#include<stdio.h>
#include<math.h>
#define fin "sequencequery.in"
#define fout "sequencequery.out"
#define Nmax 1000001
#define Inf 100000L*100000L
int n,m,segm[Nmax][3],best,min;
int a,b,val1,val2,val3;
FILE *in,*out;

inline int maxf(int a,int b) { (a<b)?(a=b):(a); return a; }
inline int minf(int a,int b) { (a>b)?(a=b):(a); return a; }

void insert(int nod,int st,int dr) {
int m;
	if (st==a && dr==a) {
		segm[nod][0]=val3;
		segm[nod][1]=val2;
		segm[nod][2]=val1;
	}

	else {
		m=(st+dr)/2;
		
		if (a<=m) 
			insert(2*nod,st,m);
		else	
			insert(2*nod+1,m+1,dr);
		
		segm[nod][0]=minf(segm[2*nod][0],segm[2*nod+1][0]);
		segm[nod][1]=maxf(segm[2*nod][1],segm[2*nod+1][1]);
		segm[nod][2]=maxf(segm[2*nod][2],segm[2*nod+1][2]);
		segm[nod][2]=maxf(segm[2*nod+1][1]-segm[2*nod][0],segm[nod][2]);

	}

}

void query(int nod,int st,int dr) {
int m;
	if (a<=st && dr<=b) {
		best=maxf(best,segm[nod][2]);
		best=maxf(best,segm[nod][1]-min);
	       	min=minf(min,segm[nod][0]);
	}

	else {
		m=(st+dr)/2;
		if (a<=m) 
			query(2*nod,st,m);
		if (b>m) 
			query(2*nod+1,m+1,dr);	
	}
}

int main() {
int i,j,tmp,sum;
	
	in=fopen(fin,"r"); out=fopen(fout,"w");

	fscanf(in,"%i%i",&n,&m);
	
	sum=0;

	for (i=1;i<Nmax;++i) segm[i][0]=segm[i][1]=segm[i][2]=-Inf;

	for (i=1;i<=n;i++) { 
		
		fscanf(in,"%i",&tmp);
		
		val3=sum;
		sum+=tmp; 
		val1=tmp; val2=sum; val3=minf(val3,sum);
		a=i;
		insert(1,1,n);	

	}
	
	for (i=1;i<=m;++i) {
		fscanf(in,"%i%i",&a,&b);
		
		best=-Inf; min=Inf;

		query(1,1,n);

		fprintf(out,"%i\n",best);
	}

	fclose(in); fclose(out);

	return 0;
}