#include <fstream>

using namespace std;
ifstream in  ("sequencequery.in");
ofstream out("sequencequery.out");

#define maxN 100000

int v[maxN+1];

struct ura{
    int val;
    int before;
    int after;
    int sum;
}aint[4*maxN];

void build(int nod,int st,int dr){
    if(st==dr){
        aint[nod].val=v[st];
        aint[nod].before=v[st];
        aint[nod].after=v[st];
        aint[nod].sum=v[st];
        return;
    }

    int mij=(st+dr)/2;
    int vst=2*nod,vdr=2*nod+1;

    build(vst,st,mij);
    build(vdr,mij+1,dr);

    aint[nod].val=max(aint[vst].val, aint[vdr].val);
    aint[nod].val=max(aint[nod].val, aint[vst].after+aint[vdr].before);

    aint[nod].sum=aint[vst].sum+aint[vdr].sum;
    aint[nod].before=max(aint[vst].before, aint[vst].sum+aint[vdr].before);
    aint[nod].after=max(aint[vdr].after, aint[vdr].sum+aint[vst].after);
}

ura query(int nod,int st,int dr,int a,int b){
    if(st==a && dr==b){
        return aint[nod];
    }

    int mij=(st+dr)/2;

    if(a>mij){
        return query(2*nod+1,mij+1,dr,a,b);
    }
    else if(mij>=b){
        return query(2*nod,st,mij,a,b);
    }
    else{
        ura res,vst,vdr;
        vst=query(2*nod,st,mij,a,mij);
        vdr=query(2*nod+1,mij+1,dr,mij+1,b);

        res.val=max(vst.val,vdr.val);
        if(vst.after+vdr.before>=res.val){
            res.val=vst.after+vdr.before;
        }

        res.sum=vst.sum+vdr.sum;
        res.before=max(vst.before, vst.sum+vdr.before);
        res.after=max(vdr.after, vdr.sum+vst.after);
        return res;
    }
}

int main(){

    int n,m;
    in>>n>>m;
    for(int i=0;i<n;i++){
        in>>v[i];
    }
    build(1,0,n-1);
    for(int i=1;i<=m;i++){
        int a,b;
        in>>a>>b;
        a--;
        b--;
        out<<query(1,0,n-1,a,b).val<<'\n';
    }
}