#include <bits/stdc++.h>

using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
const long long cst=1e5;
struct arb
{
    long long pref,suf,sum,secvmax;
} aint[4*cst+5];
long long v[cst+5];
void upnod(arb &a,arb a1,arb a2)
{
    a.sum=a1.sum+a2.sum;
    a.pref=max(a1.pref,a1.sum+a2.pref);
    a.suf=max(a2.suf,a2.sum+a1.suf);
    a.secvmax=max(a1.suf+a2.pref,max(a1.secvmax,a2.secvmax));
}
void build(long long nod,long long l,long long r)
{
    if(l==r)
    {
        aint[nod].pref=v[l];
        aint[nod].suf=v[l];
        aint[nod].sum=v[l];
        aint[nod].secvmax=v[l];
    }
    else
    {
        long long mij=(l+r)/2;
        build(nod*2,l,mij);
        build(nod*2+1,mij+1,r);
        upnod(aint[nod],aint[nod*2],aint[nod*2+1]);
    }
}
arb query(long long nod,long long l,long long r,long long ql,long long qr)
{
    if(ql<=l&&r<=qr)
    {
        return aint[nod];
    }
    else
    {
        long long mij=(l+r)/2;
        if(qr<=mij)
        {
            return query(2*nod,l,mij,ql,qr);
        }
        else if(ql>=mij+1)
        {
            return query(2*nod+1,mij+1,r,ql,qr);
        }
        else
        {
            arb a,a1=query(2*nod,l,mij,ql,qr),a2=query(2*nod+1,mij+1,r,ql,qr);
            upnod(a,a1,a2);
            return a;
        }
    }
}
int main()
{
    long long n,m;
    fin>>n>>m;
    for(long long i=1; i<=n; i++)
    {
        fin>>v[i];
    }
    build(1,1,n);
    for(long long i=1; i<=m; i++)
    {
        long long x,y;
        fin>>x>>y;
        arb sol=query(1,1,n,x,y);
        fout<<sol.secvmax<<'\n';
    }
    return 0;
}