#include <fstream>
#include <vector>
#include <queue>
#define INF 2e9
using namespace std;
ifstream fin ("sequencequery.in");
ofstream fout("sequencequery.out");
int i,j,Q,n,t,x,y,val,m,V[100005],sol;
struct elem
{
    long long suma,st,dr,ssm;
}A[400003];
elem U(elem x,elem y)
{
    elem z;
    z.suma=x.suma+y.suma;
    z.st=max(x.st,x.suma+y.st);
    z.dr=max(y.dr,y.suma+x.dr);
    z.ssm=max(y.st+x.dr,max(x.ssm,y.ssm));
    return z;
}
void build(int nod,int st,int dr)
{
    if(st==dr)
        A[nod]={V[st],V[st],V[st],V[st]};
    else
    {
        int mid=(st+dr)/2;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);
        A[nod]=U(A[2*nod],A[2*nod+1]);
    }
}
elem query(int nod,int st,int dr,int a,int b)
{
    if(a<=st&&dr<=b)
        return A[nod];
    else
    {
        int mid=(st+dr)/2;
        if(a<=mid&&mid+1<=b)
            return U(query(2*nod,st,mid,a,b),query(2*nod+1,mid+1,dr,a,b));
        if(a<=mid)
            return query(2*nod,st,mid,a,b);
        if(mid+1<=b)
            return query(2*nod+1,mid+1,dr,a,b);
    }
}
int main()
{
    fin>>n>>Q;
    for(i=1;i<=n;i++)
        fin>>V[i];
    build(1,1,n);
    while(Q--)
    {
        fin>>x>>y;
        fout<<query(1,1,n,x,y).ssm<<"\n";
    }
    return 0;
}