#include <iostream>
#include <fstream>
#include <algorithm>

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

const int NMAX=4e5+5;
int v[NMAX];

struct elem{
    long long sum;
    long long before;
    long long after;
    long long ssm;
}aint[NMAX];

elem solve(elem l,elem r)
{
    elem kon;
    kon.sum=l.sum+r.sum;
    kon.before=max(l.before,l.sum+r.before);
    kon.after=max(r.after,r.sum+l.after);
    kon.ssm=max(r.before+l.after,max(l.ssm,r.ssm));
    return kon;
}

void update(int p,int st,int dr)
{
    int mij;
    if(st==dr)
    {
        aint[p]={v[st],v[st],v[st],v[st]};
        return ;
    }
    else
    {
        mij=st+dr;
        mij/=2;
        update(2*p,st,mij);
        update(2*p+1,mij+1,dr);
        aint[p]=solve(aint[2*p],aint[2*p+1]);
    }
}

elem query(int p,int st,int dr,int l,int r)
{
    int mij;
    elem a,b;
    if(l<=st && dr<=r)
        return aint[p];
    else
    {
       mij=st+dr;
       mij/=2;
       if(r<=mij)
            return query(2*p,st,mij,l,r);
       if(mij<l)
            return query(2*p+1,mij+1,dr,l,r);
       a=query(2*p,st,mij,l,r);
       b=query(2*p+1,mij+1,dr,l,r);
       return solve(a,b);
    }
}

int main()
{
    int n,q,i,j,x,y;
    fin>>n>>q;
    for(i=1;i<=n;i++)
        fin>>v[i];
    update(1,1,n);
    while(q--)
    {
        fin>>x>>y;
        fout<<query(1,1,n,x,y).ssm<<"\n";
    }
    return 0;
}