#include <fstream>
#define DIM 100011
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
int n,m;
int a[DIM];

struct arbore{
    long long smax,st,dr,sum;
};
arbore v[4*DIM+1];

void construct(int nod,int p,int u){
    if(p==u){
        v[nod].smax=v[nod].sum=v[nod].dr=v[nod].st=a[p];
        return;
    }
    int mid=p+(u-p)/2;
    construct(2*nod,p,mid);
    construct(2*nod+1,mid+1,u);
    v[nod].sum=v[2*nod].sum+v[2*nod+1].sum;
    v[nod].smax=max(v[2*nod+1].smax,v[2*nod].smax);
    v[nod].smax=max(v[nod].smax,v[2*nod].dr+v[2*nod+1].st);
    v[nod].st=max(v[2*nod].st,v[2*nod].sum+v[2*nod+1].st);
    v[nod].dr=max(v[2*nod+1].dr,v[2*nod+1].sum+v[2*nod].dr);
}

arbore query(int nod,int p,int u,int A,int B){
    arbore r1,r2,r;
    r1.st=r2.st=r.st=0;
    r1.dr=r2.dr=r.dr=0;
    r.smax=r1.smax=r2.smax=0;
    r.sum=r1.sum=r2.sum=0;
    int st=-1,dr=-1;
    if(A<=p && u<=B)
        return v[nod];
    int mid=p+(u-p)/2;
    if(A<=mid)
        r1=query(2*nod,p,mid,A,B),st=1;
    if(B>mid)
        r2=query(2*nod+1,mid+1,u,A,B),dr=1;
    if(st==dr==1){
        r.sum=r1.sum+r2.sum;
        r.st=max(r1.st,r1.sum+r2.st);
        r.dr=max(r2.dr,r2.sum+r1.dr);
        r.smax=max(r1.dr+r2.st,r1.smax);
        r.smax=max(r.smax,r2.smax);
        return r;
    }
    if(st==1)
        return r1;
    if(dr==1)
        return r2;

}

int main(void){
    register int i,j,A,B;
    arbore r;

    f>>n>>m;
    for(i=1;i<=n;i++)
        f>>a[i];
    a[0]=0;
    construct(1,1,n);
    for(i=1;i<=m;i++){
        f>>A>>B;
        r=query(1,1,n,A,B);
        g<<r.smax<<"\n";
    }
    f.close();
    g.close();
    return 0;
}