#include <stdio.h>
#define LL long long
const int N = 100005;
struct nodArb
{
    LL vst,v,vdr;
};

int n,m,i,k,x,y,soly;
LL v[N],s[N];
nodArb arb[4*N],sol;
bool oldSol;

LL max(LL a,LL b)
{
    if(a>b)
        return a;
    return b;
}
LL sum(int i,int j)
{
    return s[j]-s[i-1];
}

nodArb uneste(nodArb nod1,int st1,int dr1, nodArb nod2,int st2,int dr2)  ///uneste 2 intervale
{
    ///nod1 este nodul din stanga
    ///nod2 este nodul din dreapta

    nodArb x;
    x.vst = max(nod1.vst, sum(st1,dr1) + nod2.vst);

    x.v = max(max(nod1.v,nod2.v) , nod1.vdr+nod2.vst);

    x.vdr = max(nod2.vdr , sum(st2,dr2) + nod1.vdr);

    return x;
}

void update(int st,int dr,int nod)
{
    //printf("%d %d %d\n",st,dr,nod);
    if(st==dr)      ///am ajuns in frunza
    {
        arb[nod].vst=arb[nod].v=arb[nod].vdr = v[i];
        return;
    }

    int m=(st+dr)/2;

    if(i<=m)        ///cautam in stanga
        update(st,m,nod*2);
    else            ///cautam in dreapta
        update(m+1,dr,nod*2+1);

    arb[nod]=uneste(arb[nod*2],st,m,arb[nod*2+1],m+1,dr);
}

void query(int st,int dr,int nod)
{
    if(st>dr)
        return;

    if(st>=x && y>=dr)  ///incluziune totala
    {
        if(oldSol == true)
        {
            oldSol = false;
            sol=arb[nod];
            soly=dr;
        }
        else
            sol=uneste(sol,x,soly,arb[nod],st,dr);
        return;
    }

    if(st>y || dr<x)    ///interval nefolositor(fara intersectie)
        return;

    int m=(st+dr)/2;

    query(st,m,nod*2);
    query(m+1,dr,nod*2+1);
}

int main()
{
    FILE *f1,*f2;
    f1=fopen("sequencequery.in","r");
    f2=fopen("sequencequery.out","w");

    fscanf(f1,"%d%d",&n,&m);

    for(i=1;i<=n;i++)
    {
        fscanf(f1,"%lld",&v[i]);
        s[i]=s[i-1]+v[i];

        k=i;
        update(1,n,1);
    }

    while(m--)
    {
        fscanf(f1,"%d%d",&x,&y);

        oldSol = true;

        query(1,n,1);

        fprintf(f2,"%lld\n",sol.v);
    }

    return 0;
}