#include <fstream>
#define inf -10000000001
#define ll long long
using namespace std;
ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");
int x,y,i,n,q,v[100001];
struct el
{
    ll sum_max,sum,sum_st,sum_dr;
};
el aint[400001],sol;
void f (el &nod,el &a,el &b)
{
    nod.sum_max=max (a.sum_dr+b.sum_st,max (a.sum_max,b.sum_max));
    nod.sum_st=max (a.sum_st,a.sum+b.sum_st);
    nod.sum_dr=max (b.sum_dr,b.sum+a.sum_dr);
    nod.sum=a.sum+b.sum;
}
void build (int nod,int st,int dr)
{
    if (st==dr)
        aint[nod].sum_max=aint[nod].sum=aint[nod].sum_st=aint[nod].sum_dr=v[st];
    else
    {
        int mij=(st+dr)/2;
        build (2*nod,st,mij);
        build (2*nod+1,mij+1,dr);
        f (aint[nod],aint[2*nod],aint[2*nod+1]);
    }
}
void query (int nod,int st,int dr)
{
    if (st>=x&&dr<=y)
        f (sol,sol,aint[nod]);
    else
    {
        int mij=(st+dr)/2;
        if (x<=mij)
            query (2*nod,st,mij);
        if (y>mij)
            query (2*nod+1,mij+1,dr);
    }
}
int main ()
{
    fin>>n>>q;
    for (i=1; i<=n; i++)
        fin>>v[i];
    build (1,1,n);
    for (i=1; i<=q; i++)
    {
        fin>>x>>y;
        sol= {inf,0,inf,inf};
        query (1,1,n);
        fout<<sol.sum_max<<"\n";
    }
    return 0;
}