#include<cstdio>
#include<algorithm>
#define Nmax 500010
using namespace std;

int N,M,add_st;
int v[Nmax],A,B,val,poz_e,s[Nmax],raspuns;

struct asd{
	int st;
	int dr;
	int m;
} a[Nmax];

void update(int nod,int st, int dr){
   if(st==dr){	
	   a[nod].m=val;
	   a[nod].st=val;
	   a[nod].dr=val;
	   return;
   }
   
   int mij=(st+dr)/2;
   
   if(poz_e <= mij)update(2*nod,st,mij);
   else update(2*nod+1,mij+1,dr);
   
   a[nod].m=max(a[2*nod].m,a[2*nod+1].m);
   
   a[nod].st = a[2*nod].st; 
   if( s[mij]-s[st-1] + a[2*nod+1].st  > a[nod].st )
	    a[nod].st =s[mij]-s[st-1] + a[2*nod+1].st ;
   
   a[nod].dr=a[2*nod+1].dr;
   if( s[dr]-s[mij] + a[2*nod].dr > a[nod].dr )
	   a[nod].dr = s[dr]-s[mij] + a[2*nod].dr;
   
   a[nod].m = max(a[nod].m,a[2*nod].dr+a[2*nod+1].st);
   a[nod].m=max(a[nod].m,max(a[nod].st,a[nod].dr));
}

void query(int nod,int st,int dr){
	if(A<=st && dr <=B){
		int c=a[nod].m;
		c=max(c,add_st+a[nod].st);
		add_st=max(add_st+s[dr]-s[st-1],a[nod].dr);
		if(raspuns < c)
			raspuns=c;
		return;
	}
	
	int mij=(st+dr)/2;
	if(A<=mij)	query(2*nod,st,mij);
	if(B>=mij+1)query(2*nod+1,mij+1,dr);
}
int main(){
	
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	
	scanf("%d%d",&N,&M);
	
	for(int i=1;i<=N;++i){
		scanf("%d",&v[i]);
		s[i]=s[i-1]+v[i];			
	}
	for(int i=1;i<=N;++i){
		poz_e=i;
		val=v[i];
		update(1,1,N);
	}
	
	for(int i=1;i<=M;++i){
		raspuns=-0x3f3f3f3f;
		scanf("%d%d",&A,&B);
		add_st=0;
		query(1,1,N);
		printf("%d\n",raspuns);
	}
	
return 0;
}