#include <stdio.h>
#define log 18
#define inf 1000000000
struct elem{long long suma,suf,pref,secv;};
elem aint[1<<log];
int val,poz,x,y;
long long rasp,sol;
long long maxim(long long a,long long b){
    if(a>b)
        return a;
    else
        return b;
}
void update(int nod,int st,int dr){
    //update pozitiza poz cu valoarea val
    if(st==dr){//nod==poz
        aint[nod].suma=val;
        aint[nod].suf=val;
        aint[nod].pref=val;
        aint[nod].secv=val;
        return ;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        update(2*nod,st,mij);
    else
        update(2*nod+1,mij+1,dr);
    aint[nod].suma=aint[2*nod].suma+aint[2*nod+1].suma;
    aint[nod].suf=maxim(aint[2*nod+1].suf,aint[2*nod].suf+aint[2*nod+1].suma);
    aint[nod].pref=maxim(aint[2*nod].pref,aint[2*nod].suma+aint[2*nod+1].pref);
    aint[nod].secv=maxim(maxim(aint[2*nod].secv,aint[2*nod+1].secv),aint[2*nod].suf+aint[2*nod+1].pref);
}
void query(int nod,int st,int dr){
    //query pe intervalul [x,y]
    if(x<=st&&dr<=y){
        if(sol<0)
            sol=0;
        rasp=maxim(rasp,maxim(aint[nod].secv,maxim(aint[nod].pref+sol,aint[nod].suma+sol)));
        sol=maxim(aint[nod].suf,sol+aint[nod].suma);
        return ;
    }
    int mij=(st+dr)/2;
    if(x<=mij)
        query(nod*2,st,mij);
    if(mij+1<=y)
        query(nod*2+1,mij+1,dr);
}
int main(){
    FILE *fin,*fout;
    fin=fopen("sequencequery.in","r");
    fout=fopen("sequencequery.out","w");
    int i,n,m;
    n=1<<log;
    /*for(i=0;i<log;i++){
        aint[i].suma=-inf;
        aint[i].suf=-inf;
        aint[i].pref=-inf;
        aint[i].secv=-inf;
    }*/
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=n;i++){
        fscanf(fin,"%d",&x);
        val=x;
        poz=i;
        update(1,1,n);
    }
    for(i=1;i<=m;i++){
        fscanf(fin,"%d%d",&x,&y);
        rasp=-inf;
        sol=0;
        query(1,1,n);
        fprintf(fout,"%lld\n",rasp);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}