#include<stdio.h>
FILE*f=fopen("sequencequery.in","r");
FILE*g=fopen("sequencequery.out","w");
long long max(long long a,long long b){
	if(a>b)
		return a;
	else 
		return b;
}
int v[100009];
long long maxx,s,a,b,n,m,i;
struct arb{
	int s;
	int d;
	int st;
	int sm;
}w[500001];
void update(int nod,int st,int dr){
	if(st==dr){
		w[nod].s=w[nod].d=w[nod].st=w[nod].sm=v[st];
		return ;
	}
	int nodst=(nod<<1);
	int noddr=nodst+1;
	int m=(st+dr)/2;
	update(nodst,st,m);
	update(noddr,m+1,dr);
	w[nod].sm=max(w[nodst].d+w[noddr].s,max(w[nodst].sm,w[noddr].sm));
	w[nod].st=w[nodst].st+w[noddr].st;
	w[nod].s=max(w[nodst].s,max(w[nod].st,w[nodst].st+w[noddr].s));
	w[nod].d=max(w[noddr].d,max(w[nod].st,w[noddr].st+w[nodst].d));
}
void query(int nod,int st,int dr){
	if(a<=st&&dr<=b){
		maxx=max(maxx,max(w[nod].sm,s+w[nod].s));
		s=max(s+w[nod].st,w[nod].d);
		return ;
	}
	int nodst=(nod<<1);
	int noddr=nodst+1;
	int m=(dr+st)/2;
	if(a<=m)
		query(nodst,st,m);
	if(b>m)
		query(noddr,m+1,dr);
}
int main() {
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=n;++i)
		fscanf(f,"%d",&v[i]);
	
	update(1,1,n);
	
	for(i=1;i<=m;++i){
		fscanf(f,"%d%d",&a,&b);
		maxx=-10000000000LL;
		s=-10000000000LL;
		query(1,1,n);
		fprintf(g,"%d\n",maxx);
	}
	
	
	fclose(g);
	fclose(f);
	return 0;
}