#include <cstdio>
#include <algorithm>
#define left (nod<<1)
#define right ((nod<<1)+1)
#define LL long long
#define Nmax 100001

using namespace std;

struct arbore
{
    LL st,dr,sum,best;
};

arbore arb[3*Nmax];
LL i,n,m,x,y,S,Max;

inline void update(int nod, int st, int dr, int poz)
{
    if (st==dr)
    {
        arb[nod].st=arb[nod].dr=arb[nod].sum=arb[nod].best=x;
        return;
    }
    LL mij=(st+dr)>>1;
    if (poz<=mij) update(2*nod,st,mij,poz);
    else update(2*nod+1,mij+1,dr,poz);

    arb[nod].sum=arb[2*nod].sum+arb[2*nod+1].sum;
    arb[nod].best=max(arb[left].dr+arb[right].st,max(arb[left].best,arb[right].best));
    arb[nod].st=max(arb[left].dr, arb[left].sum+arb[right].st);
    arb[nod].dr=max(arb[right].dr, arb[right].sum+arb[left].dr);
}

inline void query(int nod, int st, int dr, int x, int y)
{
    if (x<=st && dr<=y)
    {
        Max=max(Max,max(arb[nod].best,S+arb[nod].st));
        S=max(S+arb[nod].sum,arb[nod].dr);
    }
    else
    {
        LL mij=(st+dr)>>1;
        if (x<=mij) query(left,st,mij,x,y);
        if (y>mij) query(right,mij+1,dr,x,y);
    }
}

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

    scanf("%I64d %I64d", &n, &m);
    for (i=1;i<=n;++i)
    {
        scanf("%I64d", &x);
        update(1,1,n,i);
    }

    for (i=1;i<=m;++i)
    {
        scanf("%I64d %I64d", &x, &y);
        Max=-Nmax; S=0;
        query(1,1,n,x,y);
        printf("%I64d\n", Max);
    }

    return 0;
}