# include <fstream>
# define DIM 270000
# define INF 1000000000000000000LL
# define a first.first
# define b first.second
# define c second.first
# define d second.second
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
pair <pair <long long,long long>,pair <long long,long long> > v[DIM];
long long n,m,i,st,dr,x,nr,nrdr;
void build(long long nod,long long st,long long dr){
    if(st==dr){
        fin>>x;
        v[nod].a=v[nod].b=v[nod].c=v[nod].d=x;
    }
    else{
        long long mij=(st+dr)/2;
        build(2*nod,st,mij);
        build(2*nod+1,mij+1,dr);
        v[nod].a=max(v[2*nod].a,v[2*nod+1].a);
        v[nod].a=max(v[nod].a,v[2*nod].c+v[2*nod+1].b);
        v[nod].b=max(v[2*nod].b,v[2*nod].d+v[2*nod+1].b);
        v[nod].c=max(v[2*nod+1].c,v[2*nod+1].d+v[2*nod].c);
        v[nod].d=v[2*nod].d+v[2*nod+1].d;
    }
}
void query(long long nod,long long st,long long dr,long long p,long long u){
    if(p<=st&&u>=dr){
        nr=max(nr,v[nod].a);
        nr=max(nr,nrdr+v[nod].b);
        nrdr=max(v[nod].c,nrdr+v[nod].d);
    }
    else{
        long long mij=(st+dr)/2;
        if(p<=mij)
            query(2*nod,st,mij,p,u);
        if(u>mij)
            query(2*nod+1,mij+1,dr,p,u);
    }
}
int main () {
    fin>>n>>m;
    build(1,1,n);
    for(i=1;i<=m;i++){
        fin>>st>>dr;
        nr=-INF;
        nrdr=-INF;
        query(1,1,n,st,dr);
        fout<<nr<<"\n";
    }
    return 0;
}