#include<cstdio>
long long n,m,a,b,i,j,p,x,INF;
struct dat{
long long s;
long long m;
long long l;
long long r;
}v[400100],r;
FILE *f,*g;
long long maxim(long long a,long long b){
if(a>b)
return a;
return b;
}
void upd(int nod,int l,int r,int p,int x) {
if(l==r){
v[nod].m=v[nod].l=v[nod].r=v[nod].s=x;
return;
}
int mid=(l+r)/2;
if(p<=mid)
upd(nod*2,l,mid,p,x);
else
upd(nod*2+1,mid+1,r,p,x);
v[nod].l=maxim( v[2*nod].l, v[2*nod].s + v[2*nod+1].l );
v[nod].r=maxim( v[2*nod+1].r ,v[2*nod+1].s + v[2*nod].r );
v[nod].m=maxim( v[2*nod].m, maxim(v[2*nod+1].m, v[2*nod].r + v[2*nod+1].l ) );
long long sum=0;
if (v[2*nod].s!=-INF && v[2*nod+1].s!=-INF)
sum=v[2*nod].s+v[2*nod+1].s;
else
sum=v[2*nod].s+v[2*nod+1].s+INF;
v[nod].s=sum;
}
dat query(int nod,int l,int r,int a,int b){
int ok=0;int okk=0,mid=(l+r)/2;
dat rl,rr,rm;
if(a<=l&&b>=r)
return v[nod];
if(a<=mid){
rl=query(nod*2,l,mid,a,b);
ok=1;
}
if(b>mid) {
rr=query(nod*2+1,mid+1,r,a,b);
okk=1;
}
if(ok&&okk) {
rm.m=maxim(rl.m,maxim(rr.m,rl.r+rr.l));
rm.l=maxim(rl.l,rl.s+rr.l);
rm.r=maxim(rr.r,rr.s+rl.r);
rm.s=rl.s+rr.s;
return rm;
}
else{
if(ok)
return rl;
else
return rr;
}
}
int main(){
f=fopen("sequencequery.in","r");
g=fopen("sequencequery.out","w");
fscanf(f,"%lld%lld",&n,&m);
INF=2000000000;
for(i=1;i<=4*n;i++)
v[i].s=v[i].m=v[i].l=v[i].r=-INF;
for(i=1;i<=n;i++){
fscanf(f,"%lld",&x);
upd(1,1,n,i,x);
}
for(i=1;i<=m;i++){
fscanf(f,"%lld%lld",&a,&b);
r=query(1,1,n,a,b);
fprintf(g,"%lld\n",r.m);
}
fclose(f);
fclose(g);
return 0;
}