#include <fstream>
using namespace std;
ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
long long i, j, n, m, cer, t, sol, a, b;
long long v[800010];
struct nod{
  long long sum; // suma subsecventei
  long long pref_maxx; // prefixul de suma maxima
  long long suf_maxx; // sufixul de suma maxima
  long long maxx; // subsecventa de suma maxima
} A[800010];
nod update_nod( nod nodst, nod noddr){
    nod node;
    node.sum=nodst.sum+noddr.sum;
    node.pref_maxx=max(nodst.pref_maxx, nodst.sum+noddr.pref_maxx);
    node.suf_maxx=max(noddr.suf_maxx, noddr.sum+nodst.suf_maxx);
    node.maxx=max(max(nodst.maxx, noddr.maxx), nodst.suf_maxx+noddr.pref_maxx);
    return node;
}
/*
void update(long long nod, long long st, long long dr, long long poz, long long val){
    if(st==dr){
        A[nod].sum=val;
        A[nod].pref_maxx=val;
        A[nod].suf_maxx=val;
        A[nod].maxx=val;
        //cout<<nod<<" "<<A[nod].sum<<" "<<A[nod].pref_maxx<<" "<<A[nod].suf_maxx<<" "<<A[nod].maxx<<"\n";
    }
    else{
        long long mid=(st+dr)/2;
        if(poz<=mid)
            update(2*nod, st, mid, poz, val);
        else
            update(2*nod+1, mid+1, dr, poz, val);
        A[nod]=update_nod(A[2*nod], A[2*nod+1]);

       // cout<<nod<<" "<<A[nod].sum<<" "<<A[nod].pref_maxx<<" "<<A[nod].suf_maxx<<" "<<A[nod].maxx<<"\n";
    }

}
*/
void build(long long nod, long long st, long long dr){
    if(st==dr){
        A[nod].sum=v[st];
        A[nod].pref_maxx=v[st];
        A[nod].suf_maxx=v[st];
        A[nod].maxx=v[st];
        //cout<<nod<<" "<<A[nod].sum<<" "<<A[nod].pref_maxx<<" "<<A[nod].suf_maxx<<" "<<A[nod].maxx<<"\n";
    }
    else{
        long long mid=(st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
        A[nod]=update_nod(A[2*nod], A[2*nod+1]);
       // cout<<nod<<" "<<A[nod].sum<<" "<<A[nod].pref_maxx<<" "<<A[nod].suf_maxx<<" "<<A[nod].maxx<<"\n";
    }
}
nod query(long long nod, long long st, long long dr, long long a, long long b){
    if(a<=st && dr<=b){
       return A[nod];
    }
    else{
        long long mid=(st+dr)/2;
        if(b<=mid)
            return query(2*nod, st, mid, a, b);
        if(mid+1<=a)
            return query(2*nod+1, mid+1, dr, a, b);
       return update_nod(query(2*nod, st, mid, a, b), query(2*nod+1, mid+1, dr, a, b));
    }
}
int main() {
    cin>>n>>t;
    for(i=1;i<=n;i++){
        cin>>v[i];
    }
    build(1, 1, n);
    for(i=1;i<=t;i++){
        cin>>a>>b;
        cout<<query(1, 1, n, a, b).maxx<<"\n";
    }


}