#include <fstream>
#include <algorithm>
using namespace std;

#define NMax 100005
#define AMax 400005
#define inf 2100000000
#define fiu1 (nod<<1)
#define fiu2 ((nod<<1)|1)
#define mij ((st+dr)>>1)

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

int n,m;
int v[NMax];

struct arb{int st,dr,best,sum;} A[AMax],sol;

arb merged(arb f1,arb f2)
{
    arb T;
    T.sum=f1.sum+f2.sum;
    T.best=max( f1.dr+f2.st , max(f1.best , f2.best) );
    T.st=max( f1.st , f1.sum+f2.st );
    T.dr=max( f2.dr , f2.sum+f1.dr );
    return T;
}

void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        A[nod].st=A[nod].dr=A[nod].best=A[nod].sum=v[st];
    }
    else
    {
        build(fiu1,st,mij);
        build(fiu2,mij+1,dr);
        A[nod]=merged(A[fiu1],A[fiu2]);
    }
}

void query(int nod,int st,int dr,int a,int b)
{
    if(a<=st && dr<=b)
    {
        sol=merged(sol,A[nod]);
    }
    else if(st!=dr)
    {
        if(a<=mij) query(fiu1,st,mij,a,b);
        if(b>mij) query(fiu2,mij+1,dr,a,b);
    }
}

int main()
{
    int i,a,b;

    f>>n>>m;
    for(i=1;i<=n;++i) f>>v[i];

    build(1,1,n);

    for(i=1;i<=m;++i)
    {
        sol.best=sol.st=sol.dr=-inf;
        sol.sum=0;

        f>>a>>b;
        query(1,1,n,a,b);
        g<<sol.best<<"\n";
    }

    f.close();
    g.close();
    return 0;
}