#include <bits/stdc++.h>
#define int long long
using namespace std;

ifstream fin ("sequencequery.in");
ofstream fout("sequencequery.out");

const int dim=100009;

struct Nod{
int sum,prefmax,sufmax,secvmax;
}aint[4*dim];

int n,m,a[dim];

Nod Merge(Nod n1,Nod n2){
    Nod nod;
    nod.sum=n1.sum+n2.sum;
    nod.prefmax=max(n1.prefmax,n1.sum+n2.prefmax);
    nod.sufmax=max(n1.sufmax+n2.sum,n2.sufmax);
    nod.secvmax=max({n1.secvmax,n2.secvmax,n1.sufmax+n2.prefmax});
    return nod;
}

void Update(int nod,int st,int dr,int pos,int val){
    if(st==dr){
        aint[nod].sum=val;
        aint[nod].prefmax=val;
        aint[nod].sufmax=val;
        aint[nod].secvmax=val;
        return;
    }

    int mij=(st+dr)/2;
    if(pos<=mij)
        Update(2*nod,st,mij,pos,val);
    else
        Update(2*nod+1,mij+1,dr,pos,val);

    aint[nod]=Merge(aint[2*nod],aint[2*nod+1]);
}

Nod Query(int nod,int st,int dr,int l,int r){
    if(l==st&&r==dr){
        return aint[nod];
    }
    int mij=(st+dr)/2;

    if(r<=mij)
        return Query(2*nod,st,mij,l,r);

    if(l>=mij+1)
        return Query(2*nod+1,mij+1,dr,l,r);
    return Merge(Query(2*nod,st,mij,l,mij),Query(2*nod+1,mij+1,dr,mij+1,r));
}

signed main(){
        fin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        fin>>x;
        Update(1,1,n,i,x);
    }
    for(int i=1;i<=m;i++){
        int st,dr;
        fin>>st>>dr;
        int ans=Query(1,1,n,st,dr).secvmax;
        fout<<ans<<'\n';
    }
}