#include <cstdio>

int t,n;
const int Q=100000;
const int INF=1999999999;
struct arbore{
    int prefix,sufix,secvmax,sum;
} arb[1<<18];

int v[Q+1];

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



void initializ(int p, int st, int dr)
{
    int mj=(st+dr)>>1;


    if(st==dr)
    {
        arb[p].prefix=arb[p].sufix=arb[p].secvmax=arb[p].sum=v[st];
        return;
    }
    initializ(2*p,st,mj);
    initializ(2*p+1,mj+1,dr);
    //int suf=arb[2*p].sufix;
    //int prf=arb[2*p+1].prefix;

    if(arb[2*p].prefix==arb[2*p].sum && arb[2*p].prefix+arb[2*p+1].prefix>arb[2*p].prefix)
        arb[p].prefix=arb[2*p].prefix+arb[2*p+1].prefix;
    else
        arb[p].prefix=arb[2*p].prefix;

    if(arb[p].prefix<arb[2*p].sum+arb[2*p+1].prefix)
        arb[p].prefix=arb[2*p].sum+arb[2*p+1].prefix;

    if(arb[2*p+1].sufix==arb[2*p+1].sum && arb[2*p+1].sufix+arb[2*p].sufix > arb[2*p+1].sufix)
        arb[p].sufix=arb[2*p+1].sufix+arb[2*p].sufix;
    else
        arb[p].sufix=arb[2*p+1].sufix;

    if(arb[p].sufix<arb[2*p+1].sum+arb[2*p].sufix)
        arb[p].sufix=arb[2*p+1].sum+arb[2*p].sufix;

    arb[p].secvmax=max(arb[2*p].secvmax,arb[2*p+1].secvmax,arb[2*p].sufix+arb[2*p+1].prefix);
    arb[p].sum=arb[2*p].sum+arb[2*p+1].sum;
}
int a,b;
int actmax=-INF,actsufix=0,actsum=0;
void rezult(int p, int st, int dr)
{
    if(a<=st && dr<=b)
    {
        if(actmax!=-INF)
            actmax=max(actmax,arb[p].secvmax,actsufix+arb[p].prefix);
        else
            actmax=arb[p].secvmax;
        if(arb[p].sufix==arb[p].sum)
            actsufix+=arb[p].sufix;
        else
            actsufix=arb[p].sufix;

        actsum+=arb[p].sum;
        return;
    }
    if(dr<a || st>b)
        return;
    int mj=(st+dr)>>1;
    rezult(2*p,st,mj);
    rezult(2*p+1,mj+1,dr);
}

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

    scanf("%d%d",&n,&t);

    for(int i=1; i<=n; i++)
        scanf("%d",&v[i]);

    initializ(1,1,n);

    for(int i=1; i<=t; i++)
    {
        actmax=-INF;
        actsum=0;
        actsufix=0;
        scanf("%d%d",&a,&b);
        rezult(1,1,n);
        printf("%d\n",actmax);

    }
    return 0;
}