#include<stdio.h>
#include<math.h>
#define fin "sequencequery.in"
#define fout "sequencequery.out"
#define Nmax 100009
#define Inf 0x3f3f3f3f
int n,m,size,v[Nmax],adr[Nmax],buc[1000][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() {
int i,j,a,b,k,ans,min1;
	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++) {
		
		ans=-Inf;

		fscanf(in,"%i%i",&a,&b);
		
		if ((a-1)%size!=0) {
			det(a,(adr[a]-1)*size);
			if (best>ans) ans=best;
		}
		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];
		}
		--k;
		min1=min;

		if (b%size!=0) {
			det(k*size+1,b);
			if (best>ans) ans=best;
			if (max-min1>ans) ans=max-min1;
		}
		
		//printf("%i\n",ans);

		fprintf(out,"%i\n",ans);
	}
	
	fclose(in); fclose(out);

	return 0;
}