#include <bits/stdc++.h>

using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int n,m,x,y;
struct da
{
    long long val,st,dr,Max;
};
vector<da> v;
void build (int nod,int st,int dr)
{
    if (st==dr)
    {
        fin>>v[nod].val;
        v[nod].Max=v[nod].val;
        v[nod].st=v[nod].val;
        v[nod].dr=v[nod].val;
    }
    else
    {
        int mij=((st+dr)>>1);
        build(2*nod,st,mij);
        build(2*nod+1,mij+1,dr);
        v[nod].val=v[2*nod].val+v[2*nod+1].val;
        v[nod].st=max(v[2*nod].st,v[2*nod].val+v[2*nod+1].st);
        v[nod].dr=max(v[2*nod+1].dr,v[2*nod+1].val+v[2*nod].dr);
        v[nod].Max=max(v[2*nod].dr+v[2*nod+1].st,max(v[2*nod].Max,v[2*nod+1].Max));
    }
}
inline da query(int nod,int fiu1,int fiu2,int st,int dr)
{
    if (st>fiu2 || dr<fiu1)
    {
        da x;
        x.val=0;
        x.st=x.dr=x.Max=-2e18;
        return x;
    }
    if (st<=fiu1 && fiu2<=dr)
        return v[nod];
    int mij=((fiu1+fiu2)>>1);
    da v1=query(2*nod,fiu1,mij,st,dr);
    da v2=query(2*nod+1,mij+1,fiu2,st,dr);
    da a;
    a.val=v1.val+v2.val;
    a.st=max(v1.st,v1.val+v2.st);
    a.dr=max(v2.dr,v2.val+v1.dr);
    a.Max=max(v1.dr+v2.st,max(v1.Max,v2.Max));
    return a;
}
int main()
{
    fin>>n>>m;
    v.resize(4*n);
    build(1,1,n);
    while (m--)
    {
        fin>>x>>y;
        da p=query(1,1,n,x,y);
        fout<<p.Max<<'\n';
    }
    return 0;
}