#include <fstream>

using namespace std;
const int NMAX = 100002;
using ll = long long;

ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");

int v[NMAX];

struct aint_node {
    ll pref, suf, sum, maxx;
}aint[4 * NMAX];

aint_node init(aint_node nod, int val) { ///pt build si update
    nod.pref = val;
    nod.suf = val;
    nod.sum = val;
    nod.maxx = val;
    return nod;
}
aint_node mergee(aint_node nod1, aint_node nod2) {
    aint_node ans;
    ans.pref = max(nod1.pref, nod1.sum + nod2.pref);
    ans.suf = max(nod2.suf, nod2.sum + nod1.suf);
    ans.sum = nod1.sum + nod2.sum;
    ans.maxx = max(max(nod1.maxx, nod2.maxx), nod1.suf + nod2.pref);
    return ans;
}

void build(int nod, int st, int dr) {
    if(st == dr) {
        aint[nod] = init(aint[nod], v[st]);
        return;
    }
    int mid = (st + dr) / 2;
    build(2 * nod + 1, st, mid);
    build(2 * nod + 2, mid + 1, dr);
    aint[nod] = mergee(aint[2 * nod + 1], aint[2 * nod + 2]);
}
aint_node query(int nod, int st, int dr, int pos1, int pos2) {
    if(st == pos1 && dr == pos2)
        return aint[nod];
    int mid = (st + dr) / 2;
    aint_node ans;
    bool ok = 0; ///am init sau nu ans-ul
    if(pos1 <= mid) {
        ans = query(2 * nod + 1, st, mid, pos1, min(mid, pos2));
        ok = 1;
    }
    if(mid < pos2) {
        if(ok)
            ans = mergee(ans, query(2 * nod + 2, mid + 1, dr, max(mid + 1, pos1), pos2));
        else
            ans = query(2 * nod + 2, mid + 1, dr, max(mid + 1, pos1), pos2);
    }
    return ans;
}
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> v[i];
    build(0, 1, n); ///ai grija, aint-ul l-am indexat de la ZERO!!!
    while(m--) {
        int l, r;
        cin >> l >> r;
        cout << query(0, 1, n, l, r).maxx << '\n';
    }
    return 0;
}