#include<cstdio>
int n,m,i,x,y;
typedef struct{long long s,d,a,m;}answer;
answer arb[500000],a;
long long max(long long a,long long b){if(a<b) return b;return a;}
void update(int poz,int s,int d)
{
	if(s==d){
		arb[poz].s=arb[poz].d=arb[poz].a=arb[poz].m=x;
		return;}
	int mij=(s+d)>>1;
	int p=poz<<1;
	if(i<=mij) update(p,s,mij);
	else update(p+1,mij+1,d);
	arb[poz].s=max(arb[p].s,arb[p].a+arb[p+1].s);
	arb[poz].d=max(arb[p+1].d,arb[p].d+arb[p+1].a);
	arb[poz].a=arb[p].a+arb[p+1].a;
	arb[poz].m=max(max(arb[p].m,arb[p+1].m),arb[p].d+arb[p+1].s);
}
answer query(int poz,int s,int d)
{
	answer a;
	if(x<=s&&y>=d){
		a.s=arb[poz].s;
		a.d=arb[poz].d;
		a.a=arb[poz].a;
		a.m=arb[poz].m;
		return a;}
	int mij=(s+d)>>1;
	if(x<=mij) {
		a=query(poz*2,s,mij);
		if(y<=mij) return a;
		else {
			answer b,c;
			b=query(poz*2+1,mij+1,d);
			c.s=max(a.s,a.a+b.s);
			c.d=max(b.d,a.d+b.a);
			c.a=a.a+b.a;
			c.m=max(max(a.m,b.m),a.d+b.s);
			return c;}}
	else return query(poz*2+1,mij+1,d);
}	

int main()
{
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;++i){
		scanf("%d",&x);
		update(1,1,n);}
	for(i=1;i<=m;++i){
		scanf("%d %d",&x,&y);
		a=query(1,1,n);
		printf("%lld\n",max(max(a.s,a.d),max(a.a,a.m)));
	}
	fclose(stdout);
	return 0;
}