#include<cstdio>
#include<algorithm>
using namespace std;
int prec,n,m,t,x,y,ok;
struct  aint
{
    int sum,dr,st,secv;
}ras,a[800004];
void refresh( aint &ras, aint x, aint y)
{
    //nodul lui x< nodul lui y
    ras.sum = x.sum + y.sum;
    ras.dr = max (y.dr, x.dr + y.sum);
    ras.st = max (x.st, x.sum + y.st);
    ras.secv = max (x.dr + y.st, max (x.secv, y.secv));
}
void update (int nod, int st, int dr, int poz, int val)
{
    if (st == dr)
    {
        a[nod]= (aint) {val,val,val,val};
        return ;
    }

    int mij = (st + dr) >> 1;

    if (poz <= mij) update (nod*2, st, mij, poz, val);
    else update (nod*2+1, mij+1, dr, poz, val);

    refresh (a[nod], a[nod*2], a[nod*2+1]);
}
void query (int nod, int st, int dr, int x, int y)
{
    if (x <= st && dr <= y)
    {
        if(ok == -1)
        {
            ras = a[nod];
            ok=0;
        }
        else
            refresh(ras, ras, a[nod]);
        return ;
    }
    int mij = (st + dr) >> 1;

    if (x <= mij)   query (nod*2, st, mij, x, y);
    if (y >= mij+1) query (nod*2+1, mij+1, dr, x, y);
}

int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    scanf ("%d",&n);
    scanf ("%d",&m);
    for (int i=1; i<=n; i++)
    {
        scanf ("%d",&x);
        update (1,1,n,i,x);
    }
    for (int i=1; i<=m; i++)
    {
        scanf ("%d %d",&x,&y);
        ok=-1;
        query (1, 1, n, x, y);
        printf ("%d\n",ras.secv);
    }
    return 0;
}