#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);
    arb[p].sum=arb[2*p].sum+arb[2*p+1].sum;

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

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

        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);
    int var,membr,init;

    for(int i=1; i<=t; i++)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n", rezult(1,1,n));
    }
    return 0;
}