#include <cstdio>
#include <algorithm>
#define ssmax first.first
#define sst first.second
#define sdr second.first
#define stot second.second

using namespace std;
FILE *fin=fopen ("sequencequery.in","r");
FILE *fout=fopen ("sequencequery.out","w");
pair < pair <long long,long long> , pair <long long,long long> > v[500001];
long long sol,qst,qdr,qtot;
int stg;
void build (int nod,int st,int dr){
    int mid,x;
    if (st==dr){
        fscanf (fin,"%d",&x);
        v[nod].ssmax=v[nod].sst=v[nod].sdr=v[nod].stot=x;
    }
    else {
        mid=(st+dr)/2;
        build (2*nod,st,mid);
        build (2*nod+1,mid+1,dr);
        v[nod].ssmax=max(v[2*nod].ssmax,max(v[2*nod+1].ssmax,v[2*nod].sdr+v[2*nod+1].sst));
        v[nod].sst=max(v[2*nod].sst,v[2*nod+1].sst+v[2*nod].stot);
        v[nod].sdr=max(v[2*nod+1].sdr,v[2*nod+1].stot+v[2*nod].sdr);
        v[nod].stot=v[2*nod].stot+v[2*nod+1].stot;
    }
}
void query (int nod,int st,int dr,int x,int y){
    int mid;
    if (x<=st && dr<=y){
        //printf ("%d %d\n",st,dr);
        if (stg==-1){
            sol=v[nod].ssmax;
            qst=v[nod].sst;
            qdr=v[nod].sdr;
            qtot=v[nod].stot;
            stg=0;
        }
        else {
            sol=max(sol,max(v[nod].ssmax,qdr+v[nod].sst));
            qst=max(qst,qst+v[nod].stot);
            qdr=max(v[nod].sdr,v[nod].stot+qdr);
            qtot+=v[nod].stot;
        }
    }
    else{
        mid=(st+dr)/2;
        if (x<=mid)
            query (2*nod,st,mid,x,y);
        if (y>mid)
            query (2*nod+1,mid+1,dr,x,y);
    }
}
int main()
{
    int n,m,i,x,y;
    fscanf (fin,"%d%d",&n,&m);
    build (1,1,n);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&x,&y);
        sol=qst=qdr=qtot=0;
        stg=-1;
        query (1,1,n,x,y);
        fprintf (fout,"%lld\n",sol);
    }
    return 0;
}