#include<stdio.h>
#include<math.h>
#define fin "sequencequery.in"
#define fout "sequencequery.out"
#define Nmax 100001
int n,m,size,adr[Nmax],v[Nmax],buc[1001][3],min,max,best;
FILE *in,*out;

void det(int st,int dr) {
int i,min1;
	min=v[st]; max=v[st];
	best=v[st]-v[st-1]; min1=v[st-1];
	for (i=st;i<=dr && i<=n;++i) {
		if (v[i]-min1>best) best=v[i]-min1;
		if (v[i]<min) min=v[i];
		if (v[i]<min1) min1=v[i];
		if (v[i]>max) max=v[i];
	}
	
}

int main() {
register int i,j,a,b,k,ans,min1,lim;
	in=fopen(fin,"r"); out=fopen(fout,"w");

	fscanf(in,"%i%i",&n,&m);
		
	for (i=1;i<=n;i++) { 
		
		fscanf(in,"%i",&v[i]);
		
		v[i]+=v[i-1]; 
	
	}
	
	size=(int)sqrt(n);
	
	k=0;
	adr[1]=1;

	for (i=1;i<=n;i+=size) {
		
		det(i,i+size-1);
		
		++k;
		buc[k][0]=min; 
		buc[k][1]=max;
		buc[k][2]=best;
		
		for (j=i+1;j<=i+size;++j) adr[j]=k+1;
	}
	
	//for (i=1;i<=k;++i) printf("%i %i %i\n",buc[i][0],buc[i][1],buc[i][2]);

	for (i=1;i<=m;i++) {
		
		fscanf(in,"%i%i",&a,&b);
		
		ans=v[a]-v[a-1];
		
		lim=a; while (lim%size && lim<b) ++lim;

		if (lim%size || (a-1)%size!=0) {

			det(a,lim);
			if (best>ans) ans=best;
			if (v[a-1]<min) min=v[a-1];
		}
		else min=v[a-1];

		for (k=adr[a];k*size<=b;++k) {
			if (buc[k][2]>ans) ans=buc[k][2];
		       	if (buc[k][1]-min>ans) ans=buc[k][1]-min;
		      	if (buc[k][0]<min) min=buc[k][0];
		}

		min1=min;
		
		lim=b;
		while (lim>a && ((lim-1)%size)!=0) --lim;

		if (b%size && lim!=a) {
			det(lim,b);
			if (best>ans) ans=best;
			if (max-min1>ans) ans=max-min1;
		}
		
		fprintf(out,"%i\n",ans);
	}
	
	fclose(in); fclose(out);

	return 0;
}