#include <fstream>

using namespace std;
ifstream cin ("sequencequery.in");
ofstream cout ("sequencequery.out");
struct nod1{
long long pr,sf,sm,stot;
}a[400001];
int v[100001];
nod1 neginf={-100000000000000000,-100000000000000000,-100000000000000000,0};
nod1 combine (nod1 s,nod1 d)
{
    nod1 p;
    p.stot=s.stot+d.stot;
    p.pr=max(s.pr,s.stot+d.pr);
    p.sf=max(d.sf,s.sf+d.stot);
    p.sm=max(s.sf+d.pr,s.sm);
    p.sm=max(p.sm,d.sm);
    return p;
}
void built (int nod,int st,int dr)
{
    if (st==dr)
    {
        a[nod].pr=v[st];
        a[nod].sf=v[st];
        a[nod].sm=v[st];
        a[nod].stot=v[st];
    }
    else
    {
        int m=(st+dr)/2;
        built(2*nod,st,m);
        built(2*nod+1,m+1,dr);
        a[nod]=combine(a[2*nod],a[2*nod+1]);
    }
}
nod1 query(int nod,int st,int dr,int x,int y)
{
    if (x<=st && dr<=y)
    {
        return a[nod];
    }
    else
    {
        int m=(st+dr)/2;
        nod1 s=neginf,d=neginf;
        if (x<=m)
        {
            s=query(2*nod,st,m,x,y);
        }
        if (y>m)
        {
            d=query(2*nod+1,m+1,dr,x,y);
        }
        return combine(s,d);
    }
}
int main()
{
    int n,q;
    cin>>n>>q;
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    built(1,1,n);
    int x,y;
    for (int i=1;i<=q;i++)
    {
        cin>>x>>y;
        cout<<query(1,1,n,x,y).sm<<'\n';
    }
    return 0;
}