#include<fstream>
using namespace std;
int n, m, i, a, b, v[100003];
struct nd{
    int su;
    int st;
    int dr;
    int ss;
};
nd A[400003], r;
void build(int st, int dr, int nod){
    if(st==dr)
        A[nod].ss=A[nod].st=A[nod].dr=A[nod].su=v[st];
    else{
        int mij=st+(dr-st)/2;
        build(st, mij, 2*nod);
        build(mij+1, dr, 2*nod+1);
        A[nod].su=A[2*nod].su+A[2*nod+1].su;
        A[nod].st=max(A[2*nod].st, A[2*nod].su+A[2*nod+1].st);
        A[nod].dr=max(A[2*nod+1].dr, A[2*nod+1].su+A[2*nod].dr);
        A[nod].ss=max(A[2*nod].dr+A[2*nod+1].st, max(A[2*nod].ss, A[2*nod+1].ss));
    }
}
nd query(int st, int dr, int nod, int a, int b){
    if(a<=st && dr<=b)
        return A[nod];
    else{
        nd r;
        int mij=st+(dr-st)/2;
        nd left, right;
        int ins=0, ind=0;
        if(a<=mij){
            left=query(st, mij, 2*nod, a, b);
            ins=1;
        }
        if(b>=mij+1){
            right=query(mij+1, dr, 2*nod+1, a, b);
            ind=1;
        }
        if(ins==ind==1){
            r.su=left.su+right.su;
            r.st=max(left.st, left.su+right.st);
            r.dr=max(right.dr, right.su+left.dr);
            r.ss=max(left.dr+right.st, max(left.ss, right.ss));
            return r;
        }
        if(ins==1)
            return left;
        if(ind==1)
            return right;
    }
}
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
int main(){
    in>>n>>m;
    for(i=1; i<=n; i++)
        in>>v[i];
    build(1, n, 1);
    for(; m--; ){
        in>>a>>b;
        r=query(1, n, 1, a, b);
        out<<r.ss<<"\n";
    }
return 0;
}