#include <fstream>
#include <algorithm>
#define DIM 100005
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
const long long INF=(1LL<<30);
int N,M;
int v[DIM];
struct nodAINT{
    long long sum;
    long long submax;
    long long sufmax;
    long long prefmax;
};
nodAINT A[4*DIM];
nodAINT update(nodAINT st,nodAINT dr){
    nodAINT sol;
    sol.sum=st.sum+dr.sum;
    sol.submax=max( max(st.submax,dr.submax) ,st.sufmax+dr.prefmax  );
    sol.prefmax=max( st.prefmax, st.sum+dr.prefmax  );
    sol.sufmax=max( dr.sufmax, dr.sum+st.sufmax );
    return sol;

}
void build(int nod,int st,int dr){
    if(st==dr){
        A[nod].sum=v[st];
        A[nod].submax=v[st];
        A[nod].sufmax=v[st];
        A[nod].prefmax=v[st];
    }
    else{
        int mid=(st+dr)/2;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);
        A[nod]=update(A[2*nod],A[2*nod+1]);
    }
}
void query(int nod,int st,int dr,int a,int b,nodAINT &maxim){
    if(a<=st && dr<=b){
        if(maxim.sum==-INF)
            maxim=A[nod];
        else
            maxim=update(maxim,A[nod]);
    }
    else{
        int mid=(st+dr)/2;
        if(a<=mid)
            query(2*nod,st,mid,a,b,maxim);
        if(b>mid)
            query(2*nod+1,mid+1,dr,a,b,maxim);
    }
}
int main()
{
    fin>>N>>M;
    for(int i=1;i<=N;i++)
        fin>>v[i];
    build(1,1,N);
    for(int i=1;i<=M;i++){
        int a,b;
        fin>>a>>b;
        nodAINT maxim={-INF,-INF,-INF,-INF};
        query(1,1,N,a,b,maxim);
        fout<<maxim.submax<<"\n";
    }
    return 0;
}