#include<stdio.h>
#define fin "sequencequery.in"
#define fout "sequencequery.out"
#define NMAX 100001
#define SMAX 1000001
long n,m,min,max,val,a,b,segm[SMAX][3]; //segm: 0-min, 1-max
FILE *in,*out;
long maxf(long a,long b) {(a<b)?(a=b):(a); return a; }
void insert(long nod,long st,long dr) {
long m,x1,y1,x2,y2;
if (a<=st && dr<=b) {
segm[nod][0]=val;
segm[nod][1]=val;
segm[nod][2]=1;
}
else {
m=(st+dr)/2;
if (a<=m) insert(2*nod,st,m);
else insert(2*nod+1,m+1,dr);
if (!segm[2*nod][2]) {
segm[nod][0]=segm[2*nod+1][0];
segm[nod][1]=segm[2*nod+1][1];
segm[nod][2]=segm[2*nod+1][2];
}
else
if (!segm[2*nod+1][2]) {
segm[nod][0]=segm[2*nod][0];
segm[nod][1]=segm[2*nod][1];
segm[nod][2]=segm[2*nod][2];
}
else {
x1=segm[2*nod][0]; x2=segm[2*nod+1][0];
y1=segm[2*nod][1]; y2=segm[2*nod+1][1];
segm[nod][2]=1;
if (x1<=x2) {
segm[nod][0]=x1;
segm[nod][1]=maxf(y1,y2);
}
else {
if (y1-x1>y2-x2) {
segm[nod][0]=x1;
segm[nod][1]=y1;
}
else {
segm[nod][0]=x2;
segm[nod][1]=y2;
}
}
}
}
}
void query(long nod,long st,long dr) {
long m,x1,y1,x2,y2;
if (a<=st && dr<=b) {
x1=min; x2=segm[nod][0];
y1=max; y2=segm[nod][1];
if (x1<=x2) {
min=x1;
max=maxf(y1,y2);
}
else {
if (y1-x1>y2-x2) {
min=x1;
max=y1;
}
else {
min=x2;
max=y2;
}
}
}
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() {
long i,k,s=0,tmp;
in=fopen(fin,"r"); out=fopen(fout,"w");
fscanf(in,"%ld%ld",&n,&m);
val=0; a=0; insert(1,0,n);
for (i=1;i<=n;i++) {
fscanf(in,"%ld",&k);
s+=k; a=i; b=i;
val=s;
insert(1,0,n);
}
for (i=1;i<=m;i++) {
fscanf(in,"%ld%ld",&a,&b);
--a;
min=NMAX; max=-NMAX;
query(1,0,n);
tmp=max-min;
fprintf(out,"%ld\n",tmp);
}
fclose(in); fclose(out);
return 0;
}