#include <fstream>
#define ll long long
#define lmin LONG_MIN
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
int n,x,y,m;
const int N=1e5+3;
int val[N];
struct lache
{
    ll sleft=lmin,sright=lmin,sall,smax=lmin;
} a[4*N];
void build(int nod,int st, int dr)
{
    if(st==dr)
    {
        a[nod]= {val[st],val[st],val[st],val[st]};
    }
    else
    {
        int mij=(st+dr)/2;
        build(nod*2,st,mij);
        build(nod*2+1,mij+1,dr);
        int l=nod*2,r=nod*2+1;
        a[nod]=
        {
            max(a[l].sleft,a[l].sall+a[r].sleft),
            max(a[r].sright,a[r].sall+a[l].sright),
            a[l].sall+a[r].sall,
            max(max(a[l].smax,a[r].smax),a[l].sright+a[r].sleft)
        };
    }
}
lache query(int nod,int st,int dr,int qst,int qdr)
{
    if(qdr<st||qst>dr)
        return {lmin,lmin,0,lmin};
    if(qst<=st&&dr<=qdr)
        return a[nod];
    int mij=(st+dr)/2;
    lache l=query(nod*2,st,mij,qst,qdr);
    lache r=query(nod*2+1,mij+1,dr,qst,qdr);
    return
    {
        max(l.sleft,l.sall+r.sleft),
        max(r.sright,r.sall+l.sright),
        l.sall+r.sall,
        max(max(l.smax,r.smax),l.sright+r.sleft)
    };
}
int main()
{
    f>>n>>m;
    for(int i=1; i<=n; i++)
        f>>val[i];
    build(1,1,n);
    while(m--)
    {
        f>>x>>y;
        g<<query(1,1,n,x,y).smax<<'\n';
    }
    return 0;
}