#include <cstdio>
#include <algorithm>
#define Nmax 100005

using namespace std;

int a[Nmax];
long long st[3*Nmax],dr[3*Nmax],val[3*Nmax],suma[3*Nmax];

struct inf
{
    long long st,dr,val,suma;
};

inline void Build(int nod, int stt, int drr)
{
    if(stt==drr)
    {
        val[nod]=st[nod]=dr[nod]=suma[nod]=a[stt];
        return;
    }
    int mij=(stt+drr)/2;
    Build(2*nod,stt,mij);
    Build(2*nod+1,mij+1,drr);
    val[nod]=max(val[2*nod],max(val[2*nod+1],dr[2*nod]+st[2*nod+1]));
    st[nod]=max(st[2*nod],suma[2*nod]+st[2*nod+1]);
    dr[nod]=max(dr[2*nod+1],suma[2*nod+1]+dr[2*nod]);
    suma[nod]=suma[2*nod]+suma[2*nod+1];
}

inline inf Query(int nod, int stt, int drr, int x, int y)
{
    inf w,w1,w2;
    if(stt==x && y==drr)
    {
        w.st=st[nod]; w.dr=dr[nod]; w.val=val[nod]; w.suma=suma[nod];
        return w;
    }
    int mij=(stt+drr)/2;
    if(y<=mij)
        return Query(2*nod,stt,mij,x,y);
    else
        if(x>mij)
            return Query(2*nod+1,mij+1,drr,x,y);
        else
        {
            w1=Query(2*nod,stt,mij,x,mij);
            w2=Query(2*nod+1,mij+1,drr,mij+1,y);
            w.val=max(w1.val,max(w2.val,w1.dr+w2.st));
            w.st=max(w1.st,w1.suma+w2.st);
            w.dr=max(w2.dr,w2.suma+w1.dr);
            w.suma=w1.suma+w2.suma;
            return w;
        }
}

int main()
{
    int N,M,x,y,i;
    freopen ("sequencequery.in","r",stdin);
    freopen ("sequencequery.out","w",stdout);
    scanf("%d%d", &N,&M);
    for(i=1;i<=N;++i)
        scanf("%d", &a[i]);
    Build(1,1,N);
    while(M--)
    {
        scanf("%d%d", &x,&y);
        printf("%lld\n", Query(1,1,N,x,y).val);
    }
    return 0;
}