#include <fstream>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

int n, m, v[100001], s[100001], i, nr, x, y;
struct{
    long long suma;
    int stg;
    int drp;
} a[400001], sol;

void build(int nod, int st, int dr){
    if(st == dr){
        a[nod].suma = v[st];
        a[nod].stg = a[nod].drp = st;
        return;
    }
    int mid = (st+dr)/2;
    build(2*nod, st, mid);
    build(2*nod+1, mid+1, dr);
    a[nod].suma = max(a[2*nod].suma, a[2*nod+1].suma);
    int stanga = a[2*nod].drp + 1;
    int dreapta = a[2*nod+1].stg - 1;
    if(stanga <= dreapta+1)
        a[nod].suma = max(a[nod].suma, a[2*nod].suma + a[2*nod+1].suma + s[dreapta] - s[stanga-1]);
    if(a[nod].suma == a[2*nod].suma)
        a[nod] = a[2*nod];
    else
        if(a[nod].suma == a[2*nod+1].suma)
            a[nod] = a[2*nod+1];
        else
            a[nod].stg = a[2*nod].stg, a[nod].drp = a[2*nod+1].drp;
}

void query(int nod, int st, int dr){
    if(x <= st && dr <= y){
        nr++;
        if(nr == 1)
            sol = a[nod];
        else{
            int d = max(sol.suma, a[nod].suma);
            int stanga = sol.drp + 1;
            int dreapta = a[nod].stg - 1;
            int h = d;
            if(stanga <= dreapta+1){
                int u = sol.suma + a[nod].suma + s[dreapta] - s[stanga-1];
                h = max(h, u);
            }
            if(sol.suma == h)
                sol = sol;
            else
                if(h == a[nod].suma)
                    sol = a[nod];
                else
                    sol.stg = sol.stg, sol.drp = a[nod].drp;
            sol.suma = h;
        }
        return;
    }
    int mid = (st+dr)/2;
    if(x <= mid)
        query(2*nod, st, mid);
    if(y > mid)
        query(2*nod+1, mid+1, dr);
}

int main(){
    fin>>n>>m;
    s[0] = 0;
    for(i=1;i<=n;i++){
        fin>>v[i];
        s[i] = s[i-1] + v[i];
    }
    build(1, 1, n);
    while(m--){
        fin>>x>>y;
        nr = 0;
        query(1, 1, n);
        fout<<sol.suma<<"\n";
    }
    return 0;
}