#include<stdio.h>
#define N 100002
int maxim (int a,int b){
	return (a>b?a:b);
}
struct tree{
	int x,y,max,tot;
};
tree v[4*N];
int w[N],i,c1,c2,rez,dif,n,m;
void cons(int st, int dr, int poz){
	if(st==dr){
		w[st]=poz;
		return ;
	}
	int q=(st+dr)/2;
	cons(st,q,2*poz);
	cons(q+1,dr,2*poz+1);
}
void update(int p){
	for(;p;p>>=1){
		v[p].tot=v[p*2].tot+v[p*2+1].tot;
		v[p].x=maxim(v[p*2].x,v[p*2].tot+v[p*2+1].x);
		v[p].y=maxim(v[p*2+1].y,v[p*2+1].tot+v[p*2].y);
		v[p].max=maxim(v[p*2].max,v[p*2+1].max);
		v[p].max=maxim(v[p].max, v[p*2].y+v[p*2+1].x);
	}
}
void query(int st, int dr, int p){
	if(st>=c1&&dr<=c2){
		rez=maxim(rez,v[p].max);
		rez=maxim(rez,dif+v[p].x);
		dif=maxim(v[p].y,dif+v[p].tot);
		return ;
	}
	if(st>c2||dr<c1||st==dr)
		return ;
	query(st,(st+dr)/2,2*p);
	query((st+dr)/2+1,dr,2*p+1);
}
int main () {
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	scanf("%d%d",&n,&m);
	cons(1,n,1);
	int q;
	for(i=1;i<=n;++i){
		scanf("%d",&q);
		int p=w[i];
		v[p].x=v[p].y=v[p].max=v[p].tot=q;
		update(p>>1);
	}
	for(i=1;i<=m;++i){
		scanf("%d%d",&c1,&c2);
		rez=dif=-(1<<30);
		query(1,n,1);
		printf("%d\n",rez);
	}
	return 0;
}