#include <bits/stdc++.h>
#define DIM 100001
#define int long long

using namespace std;

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

struct nod{

    int pref, suff, sum, answer, size;

};

vector <nod> wmt(4 * DIM);

nod Combine(nod st, nod dr){

    nod answer;

    answer.size = st.size + dr.size;

    answer.sum = st.sum + dr.sum;

    answer.pref = max(st.pref, st.sum + dr.pref);

    answer.suff = max(dr.suff, dr.suff + dr.sum);

    answer.answer = max(st.answer,
                        max(dr.answer,
                            max(
                                max(answer.pref, answer.suff), st.suff + dr.pref)));

    return answer;

}

void Build_Tree(int node, int st, int dr){

    if(st == dr){

        fin >> wmt[node].answer;

        wmt[node].pref = wmt[node].answer;

        wmt[node].suff = wmt[node].answer;

        wmt[node].sum = wmt[node].answer;

        wmt[node].size = 1;

    }

    else {

        int mij = (st + dr) >> 1;

        Build_Tree(node << 1, st, mij);
        Build_Tree(node << 1 | 1, mij + 1, dr);

        wmt[node] = Combine(wmt[node << 1], wmt[node << 1 | 1]);

    }

}

nod INF;

nod Query(int node, int st, int dr, int a, int b){

    if(dr < a || st > b)
        return INF;

    if(st >= a && dr <= b)
        return wmt[node];

    else {

        int mij = (st + dr) >> 1;

        nod ok1 = Query(node << 1, st, mij, a, b);
        nod ok2 = Query(node << 1 | 1, mij + 1, dr, a, b);

        return Combine(ok1, ok2);

    }

}

int n, i, Q, st, dr, task;

int32_t main(){

    INF.answer = -2e9;

    INF.pref = -2e9;

    INF.suff = -2e9;

    INF.size = 1e9;

    fin >> n >> Q;

    Build_Tree(1, 1, n);

    while(Q--){

        fin >> st >> dr;

        fout << Query(1, 1, n, st, dr).answer << "\n";

    }

    fin.close();
    fout.close();

    return 0;

}