#include <bits/stdc++.h>

using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
struct arbore
{
    long long  a,b,c,s;
}arb[400005];
void update (long long  st,long long  dr,long long  nod,long long  poz,long long  val)
{
    if (st==dr)
    {
        arb[nod].a=val;
        arb[nod].b=val;
        arb[nod].c=val;
        arb[nod].s=val;
        return;
    }
    long long  mij=(st+dr)/2;
    if (poz<=mij)
    {
        update(st,mij,2*nod,poz,val);
    }
    else
    {
        update(mij+1,dr,2*nod+1,poz,val);
    }
    arb[nod].a=max(arb[2*nod].a,arb[2*nod].s+arb[2*nod+1].a);
    arb[nod].b=max(arb[2*nod+1].b,arb[2*nod+1].s+arb[2*nod].b);
    arb[nod].c=max(arb[2*nod].b+arb[2*nod+1].a,max(arb[2*nod].c,arb[2*nod+1].c));
    arb[nod].s=arb[2*nod].s+arb[2*nod+1].s;
}
long long  s,ans;
void query (long long  st,long long  dr,long long  nod,long long  ua,long long  ub)
{
    if (ua<=st&&dr<=ub)
    {
        ans=max(ans,max(s+arb[nod].a,arb[nod].c));
        s=max(s+arb[nod].s,arb[nod].b);
        return ;
    }
    long long  mij=(st+dr)/2;
    if (ua<=mij)
    {
        query(st,mij,2*nod,ua,ub);
    }
    if (mij<ub)
    {
        query(mij+1,dr,2*nod+1,ua,ub);
    }
}
long long  n,i,v[100005],q,x,y;
int main()
{
    f>>n>>q;
    for (i=1;i<=n;i++)
    {
        f>>v[i];
        update(1,n,1,i,v[i]);
    }
    for (i=1;i<=q;i++)
    {
        f>>x>>y;
        s=ans=-100001;
        query (1,n,1,x,y);
        g<<ans<<'\n';
    }
    return 0;
}