#include <fstream>
using namespace std;
typedef long long ll;
const int nmax=1e5+3;
const long long inf=(1ll<<60);
ifstream f ("sequencequery.in");
ofstream g ("sequencequery.out");
struct usu
{
  ll sol,st,dr,tot;
}arb[4*nmax];
int v[nmax],x,y,n,m;
ll res,drt;
void gioto(int nod,int st,int dr)
{
    usu &a=arb[2*nod];
    usu &b=arb[2*nod+1];
    arb[nod].sol=max(a.dr+b.st,max(a.sol,b.sol));
    arb[nod].st=max(a.st,a.tot+b.st);
    arb[nod].dr=max(b.dr,a.dr+b.tot);
    arb[nod].tot=a.tot+b.tot;
}
void fuk(int nod,int st,int dr)
{
    if(st==dr)
    {
        arb[nod]={v[st],v[st],v[st],v[st]};
        return;
    }
    int mid=(st+dr)/2;
    fuk(2*nod,st,mid);
    fuk(2*nod+1,mid+1,dr);
    gioto(nod,st,dr);
}
void query(int nod,int st,int dr,int x,int y)
{
    if(x<=st&&dr<=y)
    {
        res=max(res,arb[nod].sol);
        res=max(res,drt+arb[nod].st);
        drt=max(drt+arb[nod].tot,arb[nod].dr);
    }
    else
    {
        int mid=(st+dr)/2;
        if(x<=mid)
        query(2*nod,st,mid,x,y);
        if(mid+1<=y) query(2*nod+1,mid+1,dr,x,y);
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;++i) f>>v[i];
    fuk(1,1,n);
    for(int i=1;i<=m;++i)
    {
        f>>x>>y;
        res=-inf;
        drt=0;
        query(1,1,n,x,y);
        g<<res<<'\n';
    }
    return 0;
}