#include <iostream>
#include <fstream>
#define int long long

using namespace std;

int n,q;

int inf=10000000000000000;

struct katius

{
    int sum;
    int pref;
    int suf;
    int best;
    katius
    ()
    {
        sum=-inf;
        pref=-inf;
        suf=-inf;
        best=-inf;
    }
}   aint[1<<20];

int max(int a, int b, int c)
{
    a=(a>b?a:b);
    c=(a>c?a:c);
    return c;
}

katius ask(int p, int st, int dr, int a, int b)
{
    katius
     act;
    if(st>b || dr<a)
    {
        return act;
    }
    if(a<=st && dr<=b)
        return aint[p];

    katius
     n1,n2;
    int md=(st+dr)/2;
    n1=ask(2*p,st,md,a,b);
    n2=ask(2*p+1,md+1,dr,a,b);

    act.sum=n1.sum+n2.sum;
    act.pref=max(n1.pref,n1.sum+n2.pref);
    act.suf=max(n2.suf, n2.sum+n1.suf);
    act.best=max(n1.best,n2.best,n1.suf+n2.pref);
    return act;

}

void update(int poz, int val, int p, int st, int dr)
{
    if(st==dr)
    {
        aint[p].sum=val;
        aint[p].pref=val;
        aint[p].suf=val;
        aint[p].best=val;
        return;
    }

    int md=(st+dr)/2;

    if(md>=poz)
        update(poz,val,2*p,st,md);
    else
        update(poz,val,2*p+1,md+1,dr);

    aint[p].sum=aint[2*p].sum+aint[2*p+1].sum;
    aint[p].pref=max(aint[2*p].pref,aint[2*p].sum+aint[2*p+1].pref);
    aint[p].suf=max(aint[2*p+1].suf,aint[2*p+1].sum+aint[2*p].suf);
    aint[p].best=max(aint[2*p].best,aint[2*p+1].best, aint[2*p].suf+aint[2*p+1].pref);
}

int32_t main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);

    cin>>n>>q;

    int x;

    for(int i=1; i<=n; i++)
    {
        cin>>x;
        update(i,x,1,1,1<<17);
    }

    int a,b;

    for(int i=1; i<=q; i++)
    {
        cin>>a>>b;

        cout<<ask(1,1,1<<17,a,b).best<<"\n";
    }

}