#include <cstdio>
#define maxn 100001
#define left(i) ( (i)<<1 )
#define right(i) (((i)<<1)|1)
int lf[maxn*3], rt[maxn*3], sol[maxn*3], sum[maxn*3], a[maxn];
int n, m;

void read()
{
	freopen("sequencequery.in","r",stdin);
	scanf("%d %d\n", &n, &m);
	for(int i=1;i<=n;++i) scanf("%d ", a+i);
}

void build(int n, int l, int r) 
{
	if(l==r)
	{
		lf[n]=rt[n]=sol[n]=a[l];
		sum[n]=a[l];
		return;
	}
	int m=(l+r)>>1;
	build(left(n), l, m);
	build(right(n), m+1, r);
	
	sum[n]=sum[left(n)]+sum[right(n)];
	lf[n]=lf[left(n)]>?(sum[left(n)]+lf[right(n)]);
	rt[n]=rt[right(n)]>?(sum[right(n)]+rt[left(n)]);
	sol[n]=sol[left(n)]>?sol[right(n)];
	sol[n]>?=rt[left(n)]+lf[right(n)];
}
int x, y;
long long S, ans;
void query(int n, int l, int r)//x, y
{
	if(x<=l && r<=y)
	{
		//if(S<0)S=0;
		ans=S+lf[n];
		ans>?=sol[n];
		S=S+sum[n];
		S>?=rt[n];
		return;
	}

	int m=(l+r)>>1;
	if(x<=m) query(left(n), l, m);
	if(y>m) query(right(n), m+1,r);
}
	
	


int main()
{
	freopen("sequencequery.out", "w",stdout);
	read();
	build(1, 1, n);
	while(m--)
	{
		scanf("%d %d\n", &x, &y);
		S=ans=0;
		
		query(1, 1, n);
		printf("%lld\n", ans);
	}
	
	
	return 0;
}