#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX =  100105;

int n, m;
int a[N_MAX];

struct Nod {
    int suma, prefix, sufix, sol;
}b[4 * N_MAX];

Nod combi (Nod x, Nod y) {
    Nod raspuns;
    raspuns.suma = x.suma + y.suma;
    raspuns.prefix = max(x.prefix, x.suma + y.prefix);
    raspuns.sufix = max(y.sufix, x.sufix + y.suma);
    raspuns.sol = max ({x.sol, y.sol, x.sufix + y.prefix});
    return raspuns;
}

void build (int nod, int st, int dr) {
    if (st == dr)
        b[nod] = {a[st], a[st], a[st], a[st]};
    else {
        int m = (st + dr) / 2;
        build (2 * nod, st, m);
        build (2 * nod + 1, m + 1, dr);
        b[nod] = combi (b[nod * 2], b[nod * 2 + 1]);
    }
}

Nod query (int nod, int st, int dr, int qst, int qdr) {
    if (qst <= st && dr <= qdr)
        return b[nod];
    int m = (st + dr) / 2;
    if (qst > m)
        return query (nod * 2 + 1, m + 1, dr, qst, qdr);
    if (qdr <= m)
        return query (nod * 2, st, m, qst, qdr);
    Nod qx = query(nod * 2, st, m, qst, qdr);
    Nod qy = query(nod * 2 + 1, m + 1, dr, qst, qdr);
    return combi(qx, qy);
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        Nod raspuns = query(1, 1, n, x, y);
        fout << raspuns.sol << "\n";
    }
    return 0;
}