#include <fstream>
#include <climits>
using namespace std;
ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
struct nodul
{
    long long smaxst;
    long long smaxdr;
   long long ssm;
    long long suma;
} ;

nodul aint[100000*4+1];

long long n,m;
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        int x;
        cin>>x;
        aint[nod].smaxst=x;
        aint[nod].smaxdr=x;
        aint[nod].ssm=x;
        aint[nod].suma=x;
    }
    else
    {
        int mid=(st+dr)/2;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);

        aint[nod].smaxst=max(aint[2*nod].smaxst,aint[2*nod].suma+aint[2*nod+1].smaxst);
        aint[nod].smaxdr=max(aint[2*nod+1].smaxdr,aint[2*nod+1].suma+aint[2*nod].smaxdr);
        aint[nod].suma=aint[2*nod].suma+aint[2*nod+1].suma;
        aint[nod].ssm=max(aint[2*nod].ssm,max(aint[2*nod+1].ssm,aint[2*nod].smaxdr+aint[2*nod+1].smaxst));

    }
}

void query(int nod,int st,int dr,int a,int b,nodul &val)
{
    if(a<=st&&dr<=b)
    {
        val.ssm=max(val.ssm,max(aint[nod].ssm,val.smaxdr+aint[nod].smaxst));

        val.smaxst=max(val.smaxst,val.suma+aint[nod].smaxst);

        val.smaxdr=max(aint[nod].smaxdr,aint[nod].suma+val.smaxdr);

        val.suma=aint[nod].suma+val.suma;
    }
    else
    {
        int mid=(st+dr)/2;
        if(a<=mid)
            query(2*nod,st,mid,a,b,val);
        if(b>mid)
            query(2*nod+1,mid+1,dr,a,b,val);


    }
}
int main()
{
    cin>>n>>m;
    build(1,1,n);
    for(int i=1; i<=m; i++)
    {
        int x;
        int y;
        nodul aux;
        aux.suma=0;
        aux.ssm=INT_MIN;
        aux.smaxdr=INT_MIN;
        aux.smaxst=INT_MIN;
        cin>>x>>y;
        query(1,1,n,x,y,aux);
        cout<<aux.ssm<<'\n';
    }
    return 0;
}