#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100005;
const long long INF = (long long) 1e15;
int v[NMAX];


struct nod {
    long long total, prefix, sufix, smax;
};
nod aint[4 * NMAX];


nod combin(nod x, nod y) {
    nod rez;
    rez.total = x.total + y.total;
    rez.prefix = max(x.prefix, x.total + y.prefix);
    rez.sufix = max(y.sufix, x.sufix + y.total);
    rez.smax = max(x.smax, max(y.smax, x.sufix + y.prefix));
    return rez;
}

void build(int x, int l, int r) {
    if (l > r) {
        return;
    }
    if (l == r) {
        aint[x].total = aint[x].prefix = aint[x].sufix = aint[x].smax = v[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * x, l, mid);
    build(2 * x + 1, mid + 1, r);
    aint[x] = combin(aint[2 * x], aint[2 * x + 1]);

}

nod query(int x, int l, int r, int ql, int qr) {
    if (l > r || qr < l || ql > r) {
        nod y;
        y.total = y.prefix = y.sufix = y.smax = -INF;
        return y;
    }
    if (ql <= l && qr >= r)
        return aint[x];
    int mid = (l + r) / 2;
    nod qst = query(2 * x, l, mid, ql, qr);
    nod qdr = query(2 * x + 1, mid + 1, r, ql, qr);
    return combin(qst, qdr);
}


int main() {

    int n, m, i, a, b;

    fin >> n >> m;
    for (i = 1; i <= n; i++) {
        fin >> v[i];
    }

    build(1, 1, n);

    for (i = 1; i <= m; i++) {
        fin >> a >> b;
        nod x = query(1, 1, n, a, b);
        fout << x.smax << "\n";
    }



    return 0;
}