#include <fstream>

using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

const long long f_mare = 2e+11;
int n, a[200005], i, k, m, t, x, y;
long long Pmin, smax, sum;
struct nod {
    long long suf, pref, suma, smax;
    nod() {
        suf = pref = suma = smax = -f_mare;
    }
}S[700005];

inline void build(int w, int l, int r) {
    if (l > r) return;
    if (l == r) {
        S[w].smax = S[w].suf = S[w].pref = S[w].suma = a[l];
        return;
    }
    int mid = (l+r)/2;
    build(2*w, l, mid);
    build(2*w+1, mid+1, r);
    S[w].suma = S[2*w].suma+S[2*w+1].suma;
    S[w].pref = max(S[2*w].pref, S[2*w].suma+S[2*w+1].pref);
    S[w].suf = max(S[2*w+1].suf, S[2*w+1].suma+S[2*w].suf);
    S[w].smax = max(max(S[2*w].smax, S[2*w+1].smax), S[2*w].suf+S[2*w+1].pref);
}

inline void query(int w, int l, int r) {
    if (x <= l && r <= y) {
        smax = max(smax, max(S[w].smax, sum + S[w].pref));
        sum = max(sum + S[w].suma, S[w].suf);
        return;
    }
    int mij = (l+r)/2;
    if (x <= mij)
        query(2*w, l, mij);
    if (mij < y)
        query(2*w+1, mij+1, r);

}

int main() {
    f >> n >> m;
    for (i = 1; i <= n; i++)
        f >> a[i];
    build(1, 1, n);
    for (; m; m--) {
        f >> x >> y;
        //x++, y++;
        smax = -f_mare;
        sum = 0;
        query(1, 1, n);
        g << smax;

        g << '\n';
    }
    return 0;
}