#include<fstream>
#define ssmax first.first
#define sst first.second
#define sdr second.first
#define suma second.second
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int n,m,i,x,y,ok,solssmax,solst,soldr,solsuma;
pair < pair< int,int > , pair < int,int > > a[400005];
void build(int nod,int st,int dr){
    if(st==dr){
        fin>>a[nod].ssmax;
        a[nod].sst=a[nod].ssmax;
        a[nod].sdr=a[nod].ssmax;
        a[nod].suma=a[nod].ssmax;
    }
    else{
        int mid=(st+dr)/2;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);
        a[nod].suma=a[2*nod].suma+a[2*nod+1].suma;
        a[nod].ssmax=max(a[2*nod].ssmax,max(a[2*nod+1].ssmax,a[2*nod].sdr+a[2*nod+1].sst));
        a[nod].sst=max(a[2*nod].sst,a[2*nod+1].sst+a[2*nod].suma);
        a[nod].sdr=max(a[2*nod+1].sdr,a[2*nod].sdr+a[2*nod+1].suma);
    }
}
void query(int nod,int st,int dr,int x,int y){
    if(x<=st&&dr<=y){
        if(ok==0){
            solssmax=a[nod].ssmax;
            solst=a[nod].sst;
            soldr=a[nod].sdr;
            solsuma=a[nod].suma;
            ok=1;
        }
        else{
            solssmax=max(solssmax,max(a[nod].ssmax,soldr+a[nod].sst));
            solst=max(solst,solst+a[nod].suma);
            soldr=max(a[nod].sdr,a[nod].suma+soldr);
            solsuma+=a[nod].suma;
        }
    }
    else{
        int mid=(st+dr)/2;
        if(x<=mid){
            query(2*nod,st,mid,x,y);
        }
        if(y>mid){
            query(2*nod+1,mid+1,dr,x,y);
        }
    }
}
int main(){
    fin>>n>>m;
    build(1,1,n);
    for(i=1;i<=m;i++){
        fin>>x>>y;
        solssmax=0;
        solst=0;
        soldr=0;
        solsuma=0;
        ok=0;
        query(1,1,n,x,y);
        fout<<solssmax<<"\n";
    }
    return 0;
}