#include <fstream>
#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;
ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");

struct nood{
    long long full;
    long long sst;
    long long sdr;
    long long ssm;
};
nood A[400050];
long long x,n,m,i,sol,sant,a,b;
void build(int nod, int st, int dr){
    if(st==dr){
        fin>>x;
    A[nod].full=x;
    A[nod].sst=x;
    A[nod].sdr=x;
    A[nod].ssm=x;
    }
    else{
        int mid=(st+dr)/2;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);
        A[nod].full=A[2*nod].full+A[2*nod+1].full;
        A[nod].sst=max(A[2*nod].sst,A[2*nod].full+A[2*nod+1].sst);
        A[nod].sdr=max(A[2*nod+1].sdr,A[2*nod].sdr+A[2*nod+1].full);
        x=max(A[2*nod].ssm,A[2*nod+1].ssm);
        A[nod].ssm=max(x,A[2*nod].sdr+A[2*nod+1].sst);
    }

}
void q(int nod,int st, int dr, int a, int b){
    if(a<=st && b>=dr){
        x=max(A[nod].ssm,A[nod].sst+sant);
        sol=max(sol,x);
        sant=max(sant+A[nod].full, A[nod].sdr);
        sol=max(sol,sant);

    }
    else{
        int mid=(st+dr)/2;
        if(a<=mid)
            q(2*nod, st, mid, a , b);
        if(b>mid)
            q(2*nod+1 , mid+1, dr, a, b);
    }
}
int main()
{   fin>>n>>m;
    build(1,1,n);
  /* for(i=1;i<=15;i++){
        fout<<A[i].ssm<<" "<<A[i].full<<" "<<A[i].sst<<" "<<A[i].sdr;
        fout<<"\n";
    }*/
    for(i=1;i<=m;i++){
        fin>>a>>b;
        sol=sant=INT_MIN;
        q(1,1,n,a,b);
        fout<<sol<<"\n";
    }
    return 0;
}