#include <fstream>
#define ssmax first.first
#define sst first.second
#define sdr second.first
#define suma second.second
using namespace std;
int n,q,i,x,y,v[200001];
ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");
pair < pair<int,int> , pair<int,int> > a[600001];
void build (int nod,int st,int dr){

    if (st == dr){
        a[nod].ssmax = v[st];
        a[nod].sst = v[st];
        a[nod].sdr = v[st];
        a[nod].suma = v[st];
    }
    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);
    }

}

pair < pair<int,int>, pair<int,int> > query (int nod,int st,int dr,int x,int y){
    pair < pair<int,int>, pair<int,int> > sol;
    if (x <= st && y >= dr)
        return a[nod];
    else{
        int mid = (st + dr) / 2;
        int ok1=1,ok2=1;
        pair < pair<int,int>, pair<int,int> > St,Dr;
        if (x <= mid){
            St = query (2*nod,st, mid,x,y);
            ok1 = 0;
        }
        if (y > mid){
            Dr = query (2*nod+1,mid+1,dr,x,y);
            ok2 = 0;
        }

        if (ok1 == 0 && ok2 == 0){
            sol.suma = St.suma + Dr.suma;
            sol.ssmax = max (St.sdr + Dr.sst,max (St.ssmax,Dr.ssmax));
            sol.sst = max (St.sst,Dr.sst + St.suma);
            sol.sdr = max (Dr.sdr,Dr.suma + St.sdr);
            return sol;
        }

        else{
            if (ok1 == 0)
                return St;
            if (ok2 == 0)
                return Dr;
        }
    }
}

int main (){

    fin>>n>>q;
    for (i=1;i<=n;i++)
        fin>>v[i];
    build (1,1,n);
    for (;q--;){
        fin>>x>>y;
        pair < pair<int,int>, pair<int,int> > sol = query (1,1,n,x,y);
        fout<<sol.ssmax<<"\n";
    }


    return 0;
}