#include <fstream>

using namespace std;

struct cel
{

    long long incep,termin,total,best;

}adi[400005];

long long n,m,t,x,y;

void update(int st,int dr,int i,int val,int nod)
{
    if (st==dr)
    {
        adi[nod].incep=val;
        adi[nod].termin=val;
        adi[nod].total=val;
        adi[nod].best=val;
    }else
    {
        int m=(st+dr)/2;
        if (i<=m) update(st,m,i,val,nod*2);else update(m+1,dr,i,val,nod*2+1);
        adi[nod].incep=adi[nod*2].incep; if (adi[nod*2].total+adi[nod*2+1].incep>adi[nod].incep) adi[nod].incep=adi[nod*2].total+adi[nod*2+1].incep;
        adi[nod].termin=adi[nod*2+1].termin; if (adi[nod*2+1].total+adi[nod*2].termin>adi[nod].termin) adi[nod].termin=adi[nod*2+1].total+adi[nod*2].termin;
        adi[nod].total=adi[nod*2].total+adi[nod*2+1].total;
        adi[nod].best=adi[nod*2].best; if (adi[nod*2+1].best>adi[nod].best) adi[nod].best=adi[nod*2+1].best; if (adi[nod].best<adi[nod*2].termin+adi[nod*2+1].incep) adi[nod].best=adi[nod*2].termin+adi[nod*2+1].incep;
    }
}

cel scoate(int st,int dr,int i,int j,int nod)
{
    if (st==i && dr==j)
    {
        return adi[nod];
    }
    else
    {
        int m=(st+dr)/2;
        if (i>m)
        {
            return scoate(m+1,dr,i,j,nod*2+1);
        }else
        if (j<=m)
        {
            return scoate(st,m,i,j,nod*2);
        }else
        {
            cel v,v2,res;
            v=scoate(st,m,i,m,nod*2);
            v2=scoate(m+1,dr,m+1,j,nod*2+1);

                    res.incep=v.incep; if (v.total+v2.incep>res.incep) res.incep=v.total+v2.incep;
                    res.termin=v2.termin; if (v2.total+v.termin>res.termin) res.termin=v2.total+v.termin;
                    res.total=v.total+v2.total;
                    res.best=v.best; if (v2.best>res.best) res.best=v2.best; if (res.best<v.termin+v2.incep) res.best=v.termin+v2.incep;

            return res;

        }
    }

}

int main()
{
    ifstream in ("sequencequery.in");
    ofstream out ("sequencequery.out");

    in>>n>>m;
    for (int i=1;i<=n;++i)
    {
        in>>t;
        update(1,100000,i,t,1);
    }

    for (int i=1;i<=m;++i)
    {
        in>>x>>y;
        cel v=scoate(1,100000,x,y,1);
        out<<v.best<<"\n";
    }

    in.close();
    out.close();
    return 0;
}