#include <fstream>

using namespace std;
ifstream cin ("sequencequery.in");
ofstream cout ("sequencequery.out");
struct arbore{
long long ssm,pr,sf,stotal;
}aint[400001];
long long v[100001];
arbore neginf={-922337203685477580,-922337203685477580,-922337203685477580,0};
arbore combine (arbore f1,arbore f2)
{
    arbore p;
    p.pr=max(f1.pr,f1.stotal+f2.pr);
    p.ssm=max(f1.pr+f2.sf,max(f1.ssm,f2.ssm));
    p.sf=max(f2.sf,f1.sf+f2.stotal);
    p.stotal=f1.stotal+f2.stotal;
    return p;
}
void built(int nod,int st,int dr)
{
    if (st==dr)
    {
        aint[nod].ssm=v[st];
        aint[nod].pr=v[st];
        aint[nod].sf=v[st];
        aint[nod].stotal=v[st];
    }
    else
    {
        int m=(st+dr)/2;
        built(2*nod,st,m);
        built(2*nod+1,m+1,dr);
        aint[nod]=combine(aint[2*nod],aint[2*nod+1]);
    }
}
arbore query (int nod,int st,int dr,int a,int b)
{
    if (a<=st && dr<=b)
    {
        return aint[nod];
    }
    else
    {
        int m=(st+dr)/2;
        arbore p,f1=neginf,f2=neginf;
        if (a<=m)
        {
            f1=query(2*nod,st,m,a,b);
        }
        if (b>m)
        {
            f2=query(2*nod+1,m+1,dr,a,b);
        }
        p=combine(f1,f2);
        return p;
    }
}
int main()
{
    int n,q;
    cin>>n>>q;
    for (int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    built(1,1,n);
    int a,b;
    for (int i=1;i<=q;i++)
    {
        cin>>a>>b;
        cout<<query(1,1,n,a,b).ssm<<'\n';
    }
    return 0;
}