#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,rl,rr,rm;
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;
    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;
}