#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
long long v[400000],vs[400000],vd[400000],maxi[400000],sma,ok;
int a,b,i,n,m,nr=1,bit=2,c,x,poz;

void pune(int nod,int s,int d)
{
    ++c;
    if(s==d)
    {
        vs[nod]=v[nod]=vd[nod]=maxi[nod]=x;
    }
    else
    {
        int mijlok=(s+d)/2;
        if(poz<=mijlok)
            pune(nod*2,s,mijlok);
        else
            pune(nod*2+1,mijlok+1,d);
        v[nod]=v[nod*2]+v[nod*2+1];
        vs[nod]=max(vs[nod*2],v[nod*2]+vs[nod*2+1]);
        vd[nod]=max(vd[nod*2]+v[nod*2+1],vd[nod*2+1]);
        maxi[nod]=max(max(maxi[nod*2],maxi[nod*2+1]),vd[nod*2]+vs[nod*2+1]);
    }
}
void cauta(int nod,int s,int d)
{
    if(a<=s && d<=b)
    {
        if(sma<0)
            sma=0;
        ok=max(ok,max(sma+vs[nod],maxi[nod]));
        sma=max(sma+v[nod],vd[nod]);
    }
    else
    {
        int mijlok=(s+d)/2;
        if(a<=mijlok)
            cauta(nod*2,s,mijlok);
        if(mijlok+1<=b)
            cauta(nod*2+1,mijlok+1,d);
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;++i)
    {
        fin>>x;
        poz=i;
        pune(1,1,n);
    }
    for(i=1;i<=m;++i)
    {
        fin>>a>>b;
        ok=-400000;
        sma=-400000;
        cauta(1,1,n);
        fout<<ok<<"\n";
    }
    /*for(i=1;i<=c;++i)
    {
        fout<<vd[i]<<" ";
        if(i+1==bit)
        {
            fout<<"\n";
            bit=bit<<1;
        }
    }*/
}