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

using namespace std;

int32_t 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<<18];

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

katius act;
bool bgbn;

void ask(int32_t p, int32_t st, int32_t dr, int a, int b)
{
    if(st>b || dr<a)
    {
        return;
    }
    if(a<=st && dr<=b)
    {
        if(bgbn==1)
        {
            bgbn=0;
            act.best=aint[p].best;
            act.pref=aint[p].pref;
            act.suf=aint[p].suf;
            act.sum=aint[p].sum;
            return;
        }

        katius next;

        next.best=max(act.best,aint[p].best,act.suf+aint[p].pref);
        next.suf=max(act.suf+aint[p].sum,aint[p].suf);
        next.pref=max(act.pref,act.sum+aint[p].pref);
        next.sum=act.sum+aint[p].sum;

        act.best=next.best;
        act.suf=next.suf;
        act.pref=next.pref;
        act.sum=next.sum;

        return;
    }

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

void update(int32_t p, int32_t st, int32_t dr)
{
    if(st==dr)
    {
        if(st>n)
            return;
        int val;
        cin>>val;

        aint[p].sum=val;
        aint[p].pref=val;
        aint[p].suf=val;
        aint[p].best=val;
        return;
    }

    int32_t md=(st+dr)/2;

    update(2*p,st,md);
    update(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()
{
    bool sync_with_stdio (bool sync = true);
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);

    cin>>n>>q;


    update(1,1,1<<17);

    int32_t a,b;

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

        bgbn=1;

        ask(1,1,1<<17,a,b);

        cout<<act.best<<"\n";
    }

}