#include <fstream>
#include <algorithm>
#include <climits>
using namespace std;
long long aints[400005];
struct numere{
   long long sumst,sumdr,sum;
}aint[400005];
void update1(int nod,int st,int dr,int poz,int val){
    if(st==dr){
        aints[nod]=val;return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij){
        update1(2*nod,st,mij,poz,val);
    }
    else if(mij+1<=poz){
        update1(2*nod+1,mij+1,dr,poz,val);
    }
    aints[nod]=aints[2*nod]+aints[2*nod+1];
}
void update2(int nod,int st,int dr,int poz,int val){
    if(st==dr){
        aint[nod].sumst=val;
        aint[nod].sumdr=val;
        aint[nod].sum=val;
        return;
    }
    int mij=(st+dr)/2;
     if(poz<=mij){
        update2(2*nod,st,mij,poz,val);
    }
    else if(mij+1<=poz){
        update2(2*nod+1,mij+1,dr,poz,val);
    }
    aint[nod].sum=max(aint[2*nod].sum,max(aint[2*nod+1].sum,max(aints[nod],aint[2*nod].sumdr+aint[2*nod+1].sumst)));
    aint[nod].sumst=max(aint[2*nod].sumst,max(aints[nod],aints[2*nod]+aint[2*nod+1].sumst));
    aint[nod].sumdr=max(aint[2*nod+1].sumdr,max(aints[nod],aints[2*nod+1]+aint[2*nod].sumdr));
}
long long max1=LLONG_MIN,max2=LLONG_MIN;int ant,cnt;
void query(int nod,int st,int dr,int a,int b){
    if(a<=st&&dr<=b){
        max1=max(max1,aint[nod].sum);cnt++;
        if(cnt==2){
            max2=max(max2,aint[ant].sumdr);
            max1=max(max1,max2+aint[nod].sumst);
        }
        else if(cnt>=3){
            max2=max(max2+aints[ant],aint[ant].sumdr);
            max1=max(max1,max2+aint[nod].sumst);
        }
        ant=nod;return;
    }
    int mij=(st+dr)/2;
    if(a<=mij){
        query(2*nod,st,mij,a,b);
    }
    if(mij+1<=b){
        query(2*nod+1,mij+1,dr,a,b);
    }
}
int main()
{
    ifstream fin("sequencequery.in");
    ofstream fout("sequencequery.out");
    int n,m,a,b;fin>>n>>m;
    for(int i=1;i<=n;i++){
        fin>>a;update1(1,1,n,i,a);update2(1,1,n,i,a);
    }
    for(int i=1;i<=m;i++){
        fin>>a>>b;max1=LLONG_MIN;max2=LLONG_MIN;cnt=0;ant=-1;cnt=0;
        query(1,1,n,a,b);fout<<max1<<'\n';
    }
    return 0;
}