#include <iostream>
#include <fstream>

using namespace std;

ifstream in("sequencequery.in");
ofstream out("sequencequery.out");

const long long inf=1LL<<60;

inline long long max(long long a, long long b, long long c){
    return max(a,max(b,c));
}

struct nod_struct{
    long long SUM,SUM_T,SUM_L,SUM_R;
}ARB[4*100002];

int n,m;


nod_struct comb(nod_struct x, nod_struct y){
    nod_struct t={-inf,-inf,-inf,-inf};
    t.SUM=x.SUM+y.SUM;
    t.SUM_L=max(x.SUM_L,x.SUM+y.SUM_L);
    t.SUM_R=max(y.SUM_R,y.SUM+x.SUM_R);
    t.SUM_T=max(x.SUM_T,y.SUM_T,x.SUM_R+y.SUM_L);
    return t;
}
void update(int nod, int st, int dr, int a, int b, int val){
    if(a<=st&&b>=dr){
        ARB[nod]={val,val,val,val};
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(nod*2,st,mij,a,b,val);
    if(b>mij)
        update(nod*2+1,mij+1,dr,a,b,val);

    ARB[nod]=comb(ARB[nod*2],ARB[nod*2+1]);
}
nod_struct query(int nod, int st, int dr, int a, int b){
    if(a<=st&&b>=dr){
        return ARB[nod];
    }
    int mij=(st+dr)/2;
    nod_struct q1={-inf,-inf,-inf,-inf},q2={-inf,-inf,-inf,-inf};

    if(a<=mij)
        q1=query(nod*2,st,mij,a,b);
    if(b>mij)
        q2=query(nod*2+1,mij+1,dr,a,b);
    return comb(q1,q2);
}
void read(){
    int x;
    in>>n>>m;
    for(int i=1;i<=n;i++){
        in>>x;
        update(1,1,n,i,i,x);
    }
}
void queries(){
    int x,y;
    for(int i=1;i<=m;i++){
        in>>x>>y;
        out<<query(1,1,n,x,y).SUM_T<<"\n";
    }
}
int main(){
    read();
    queries();
    return 0;
}