#include <fstream>
#define dim 20000000
using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
struct arbore{
    long long s=-dim,m=-dim,l=-dim,r=-dim;
}v[400002];
int n,m,i,x,poz,a,b;
void update(int nod,int p,int u){
    if(p==u){
        v[nod].m=v[nod].l=v[nod].r=v[nod].s=x;
        return;
    }
    int m=(p+u)/2;
    if(poz<=m)
        update(2*nod,p,m);
    else
        update(2*nod+1,m+1,u);
    v[nod].l=max(v[2*nod].l,v[2*nod].s+v[2*nod+1].l);
    v[nod].r=max(v[2*nod+1].r,v[2*nod+1].s+v[2*nod].r);
    v[nod].m=max(v[2*nod].m,max(v[2*nod+1].m,v[2*nod].r+v[2*nod+1].l));
    long long sum=0;
    if (v[2*nod].s!=-dim && v[2*nod+1].s!=-dim)
        sum=v[2*nod].s+v[2*nod+1].s;
    else
        sum=v[2*nod].s+v[2*nod+1].s+dim;
        v[nod].s=sum;
}
arbore query(int nod,int p,int u){
    if(p>=a && u<=b)
        return v[nod];
    int m=(p+u)/2,ok1=0,ok2=0;
    arbore x,y,z;
    if(m>=a){
        x=query(2*nod,p,m);
        ok1=1;
    }
    if(m<b){
        y=query(2*nod+1,m+1,u);
        ok2=1;
    }
    if(ok1 && ok2){
        z.m=max(x.m,max(y.m,x.r+y.l));
        z.l=max(x.l,x.s+y.l);
        z.r=max(y.r,y.s+x.r);
        z.s=x.s+y.s;
        return z;
    }else{
        if(ok1)
            return x;
        else
            return y;
    }
}
int main(){
    fin>>n>>m;
    for(i=1;i<=n;i++){
        fin>>x;
        poz=i;
        update(1,1,n);
    }
    for(i=1;i<=m;i++){
        fin>>a>>b;
        fout<<query(1,1,n).m<<'\n';
    }
    fin.close();fout.close();
    return 0;
}