#include<cstdio>
#include<algorithm>
using namespace std;
FILE*in=fopen("sequencequery.in","r");
FILE*out=fopen("sequencequery.out","w");
const int INF=-100001;
int n,m,a,b,i,po,r=INF,pm=0;
struct str
{
    int sum,seq,pref,suf;
};
str v[400006];
void up(int poz,int val,int nod,int nodst,int noddr)
{
    if(nodst==noddr)
    {
        v[nod].sum=val;
        v[nod].seq=val;
        v[nod].pref=val;
        v[nod].suf=val;
        return;
    }
    int mij=(nodst+noddr)/2;
    if(poz<=mij)
    {
        up(poz,val,nod*2,nodst,mij);
    }
    else
    {
        up(poz,val,nod*2+1,mij+1,noddr);
    }
    v[nod].sum=v[nod*2].sum+v[nod*2+1].sum;
    v[nod].seq=max(v[nod*2].seq,max(v[nod*2+1].seq,v[nod*2].pref+v[nod*2+1].suf));
    v[nod].pref=max(v[nod*2].pref+v[nod*2+1].sum,v[nod*2+1].pref);
    v[nod].suf=max(v[nod*2+1].suf+v[nod*2].sum,v[nod*2].suf);
}
void qer(int st,int dr,int nod,int nodst,int noddr)
{
    int mij=(nodst+noddr)/2;
    if(st==nodst&&dr==noddr)
    {
        r=max(r,max(v[nod].seq,v[nod].suf+pm));
        pm=max(v[nod].pref,pm+v[nod].sum);
        return;
    }
    else if(dr<=mij)
    {
        qer(st,dr,nod*2,nodst,mij);
    }
    else if(st>mij)
    {
        qer(st,dr,nod*2+1,mij+1,noddr);
    }
    else
    {
        qer(st,mij,nod*2,nodst,mij);
        qer(mij+1,dr,nod*2+1,mij+1,noddr);
    }
}
int main()
{
    fscanf(in,"%d%d",&n,&m);
    po=1;
    while(po<n)
    {
        po*=2;
    }
    for(i=1;i<=n;i++)
    {
        fscanf(in,"%d",&a);
        up(i,a,1,1,po);
    }
    for(i=n+1;i<=po;i++)
    {
        up(i,INF,1,1,po);
    }
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&a,&b);
        r=INF;
        pm=0;
        qer(a,b,1,1,po);
        fprintf(out,"%d\n",r);
    }
}