#include<fstream>
#define DIM 100005
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
struct str{
    int s;
    int sst;
    int sdr;
    int smax;
};
str A[4*DIM];
int v[DIM];
void build(int nod,int st,int dr){
    if(st==dr){
        A[nod].s=A[nod].sdr=A[nod].smax=A[nod].sst=v[st];
    }else{
        int mid=(st+dr)/2;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);
        A[nod].s=A[2*nod].s+A[2*nod+1].s;
        A[nod].sst=max( A[2*nod].sst , A[2*nod].s + A[2*nod+1].sst );
        A[nod].sdr=max( A[2*nod+1].sdr , A[2*nod+1].s + A[2*nod].sdr );
        A[nod].smax=max( A[2*nod].smax ,max( A[2*nod+1].smax , A[2*nod].sdr + A[2*nod+1].sst));
    }
}
str query(int nod,int st,int dr,int a,int b){
    str r;
    if(a<=st && dr<=b){
        return A[nod];
    }else{
        int mid=(st+dr)/2;
        str stanga,dreapta;
        int oks=0,okd=0;
        if(a<=mid){
            stanga=query(2*nod,st,mid,a,b);
            oks=1;
        }
        if(b>mid){
            dreapta=query(2*nod+1,mid+1,dr,a,b);
            okd=1;
        }
        if(oks==0){
            return dreapta;
        }else{
            if(okd==0){
                return stanga;
            }else{
                r.s=stanga.s+dreapta.s;
                r.sst=max(stanga.sst,stanga.s+dreapta.sst);
                r.sdr=max(dreapta.sdr,dreapta.s+stanga.sdr);
                r.smax=max(stanga.smax,max(dreapta.smax,stanga.sdr+dreapta.sst));
                return r;
            }
        }
    }
}
int x,y,n,m,i;
int main(){
    fin>>n>>m;
    for(i=1;i<=n;i++){
        fin>>v[i];
    }
    build(1,1,n);
    str rez;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        rez=query(1,1,n,x,y);
        fout<<rez.smax<<"\n";
    }
    return 0;
}