#include<fstream>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
const int Nmax = 100000;
struct inter{
    long long total,left,right,ans;
} A[18*Nmax];
int v[Nmax];
int N,M;
inter Query(int wherea,int whereb,int st,int dr,int i){
    if(wherea<=st && dr<=whereb) return A[i];
    int mij=(st+dr)/2;
    if(wherea<=mij && mij<whereb){
        inter left=Query(wherea,mij,st,mij,2*i);
        inter right=Query(mij+1,whereb,mij+1,dr,2*i+1);
        inter best;
        best.total=left.total+right.total;
        best.left=max(left.left,left.total+right.left);
        best.right=max(right.right,right.total+left.right);
        best.ans=max(max(left.ans,right.ans),left.right+right.left);
        return best;
    }
    else{
        if(whereb<=mij) return Query(wherea,whereb,st,mij,2*i);
        else return Query(wherea,whereb,mij+1,dr,2*i+1);
    }
}
void Update(int where,int st,int dr,int i){
    int mij=(st+dr)/2;
    if(where<=st && dr<=where){
        A[i].total=A[i].left=A[i].right=A[i].ans=v[where];
    }
    else{
        if(where<=mij) Update(where,st,mij,2*i);
        else Update(where,mij+1,dr,2*i+1);
        inter left=A[2*i];
        inter right=A[2*i+1];
        A[i].total=left.total+right.total;
        A[i].left=max(left.left,left.total+right.left);
        A[i].right=max(right.right,right.total+left.right);
        A[i].ans=max(max(left.ans,right.ans),left.right+right.left);
    }
}
int main(){
    in>>N>>M;
    for(int i=1;i<=N;i++){
        in>>v[i];
        Update(i,1,N,1);
    }
    for(int i=1;i<=M;i++){
        int a,b;
        in>>a>>b;
        out<<Query(a,b,1,N,1).ans<<'\n';
    }
    return 0;
}