#include <fstream>

using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int n,m,v[100001],x,y,suma,smaxst,smaxdr,ssm,nr;
struct nod
{
    int ssm,smaxst,smaxdr,suma;
}a[400001];
struct numar
{
    int nod,st, dr;
}b[100001];
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        a[nod]={v[st],v[st],v[st],v[st]};

    }
    else
    {

        int mid=(st+dr)/2;
        build(nod*2,st,mid);
        build(nod*2+1,mid+1,dr);
        a[nod].smaxst=max(a[2*nod].smaxst,a[2*nod].suma+a[2*nod+1].smaxst);
         a[nod].smaxdr=max(a[2*nod+1].smaxdr,a[2*nod].smaxdr+a[2*nod+1].suma);
         a[nod].suma=a[nod*2].suma+a[nod*2+1].suma;
        a[nod].ssm=max(a[2*nod].ssm,a[2*nod+1].ssm);
        a[nod].ssm=max(a[nod].ssm,a[2*nod].smaxdr+a[2*nod+1].smaxst);



    }
}
void caut(int nod,int st,int dr,int ac,int bc)
{
    if(ac<=st && dr<=bc)
    {

        ssm=max(ssm,max(a[nod].ssm,smaxdr+a[nod].smaxst));
        smaxst=max(smaxst,suma+a[nod].smaxst);
        smaxdr=max(a[nod].smaxdr,a[nod].suma+smaxdr);
        suma=a[nod].suma+suma;
    }
    else
    {
        int mid=(st+dr)/2;
        if(ac<=mid)
        {
            caut(nod*2,st,mid,ac,bc);

        }
        if(bc>mid)
            caut(nod*2+1,mid+1,dr,ac,bc);
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;

        suma=0,smaxst=-100001,smaxdr=-100001,ssm=-100001;
        caut(1,1,n,x,y);

        fout<<ssm<<"\n";

    }

    return 0;
}