# include <fstream>
# define DIM 100010
# define INF 10000000000LL
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
struct arbore{
    long long s,st,dr,val;
}arb[4*DIM];
int v[DIM],n,q,i,p,u;
long long drmax,maxim;
void build(int nod,int st,int dr){
    if(st==dr){
        arb[nod].val=arb[nod].st=arb[nod].dr=arb[nod].s=v[st];
        return;
    }
    int mij=(st+dr)/2;
    build(2*nod,st,mij);
    build(2*nod+1,mij+1,dr);
    arb[nod].s=arb[2*nod].s+arb[2*nod+1].s;
    arb[nod].st=max(arb[2*nod].s+arb[2*nod+1].st,arb[2*nod].st);
    arb[nod].dr=max(arb[2*nod+1].s+arb[2*nod].dr,arb[2*nod+1].dr);
    arb[nod].val=max(arb[2*nod].val,arb[2*nod+1].val);
    arb[nod].val=max(arb[nod].val,arb[2*nod].dr+arb[2*nod+1].st);
}
void query(int nod,int st,int dr,int p,int u){
    if(p<=st&&u>=dr){
        maxim=max(maxim,arb[nod].val);
        maxim=max(maxim,drmax+arb[nod].st);
        drmax=max(drmax+arb[nod].s,arb[nod].dr);
        return;
    }
    if(st>=dr)
        return;
    int 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>>q;
    for(i=1;i<=n;i++)
        fin>>v[i];
    build(1,1,n);
    for(i=1;i<=q;i++){
        fin>>p>>u;
        maxim=-INF;
        drmax=-INF;
        if(p>u)
            swap(p,u);
        query(1,1,n,p,u);
        fout<<maxim<<"\n";
    }
    return 0;
}