#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].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);
        a[nod].smaxst=max(a[2*nod].smaxst,a[2*nod].suma+a[2*nod+1].smaxst);
        a[nod].smaxdr=max(a[2*nod].smaxdr,a[2*nod].smaxdr+a[2*nod+1].suma);
        a[nod].suma=a[nod*2].suma+a[nod*2+1].suma;
    }
}
void caut(int nod,int st,int dr,int ac,int bc)
{
    if(ac<=st && dr<=bc)
    {

        b[++nr]={nod,st,dr};
    }
    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);
    }
}
void prel()
{
    for(int i=1;i<=nr;i++)
    {
        int nod=b[i].nod;
        int st=b[i].st;
        int dr=b[i].dr;
        int noda=b[i-1].nod;
        int nodu=b[i+1].nod;
        smaxst=max(smaxdr,smaxst+a[nod].suma);
        suma=suma+a[nod].suma;
        ssm=max(ssm,a[nod].ssm);

        ssm=max(a[nod].ssm,smaxdr+a[noda].smaxst);

    }
}
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;
        nr=0;
        suma=0,smaxst=-100001,smaxdr=-100001,ssm=-100001;
        caut(1,1,n,x,y);
        prel();
        fout<<ssm<<"\n";

    }

    return 0;
}