#include <bits/stdc++.h>
#define INF 100005

using namespace std;

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

typedef long long ll;
struct tree_node {
    ll suma;
    ll pref;
    ll suf;
    ll secv;
};

vector<tree_node> segm_tree(500005);
vector<int> val(100005);


tree_node update_node(tree_node nod1, tree_node nod2) {

    tree_node actnod;

    actnod.suma = nod1.suma + nod2.suma;

    actnod.pref = max(nod1.pref, nod1.suma + nod2.pref);

    actnod.suf = max(nod2.suf, nod2.suma + nod1.suf);

    actnod.secv = max(nod1.suf + nod2.pref, max(nod1.secv, nod2.secv));


    return actnod;

}


void build(int node, int left, int right) {

    if (left == right) {
        segm_tree[node].suma = val[left];
        segm_tree[node].pref = val[left];
        segm_tree[node].suf = val[left];
        segm_tree[node].secv = val[left];
    }
    else {

        int mij = (left + right) / 2;
        build(node * 2, left, mij);
        build(node * 2 + 1, mij + 1, right);
        segm_tree[node] = update_node(segm_tree[node*2],segm_tree[node*2+1]);
    }
}


tree_node query(int node, int left, int right, int left_q, int right_q) {

    if (right<left || left>right_q || right < left_q) {
        tree_node aux;
        aux.pref = -INF;
        aux.suma = -INF;
        aux.suf = -INF;
        aux.secv = -INF;
        return aux;
    }

    if (left_q <= left && right <= right_q) {
        return segm_tree[node];

    }
    else {
        int mij = (left + right) / 2;

        return update_node(query(node * 2, left, mij, left_q, right_q), query(node * 2 + 1, mij + 1, right, left_q, right_q));

    }

}





int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    int n,m;
    fin >> n>>m;
    
    for (int i = 1; i <= n; i++) {
        fin>>val[i];
    }
    build(1, 1, n);
    int a, b;
    for (int i = 1; i <= m; i++) {
        fin >> a >> b;
        fout << query(1, 1, n, a, b).secv<<'\n';
    }



    fin.close();
    fout.close();
    return 0;
}