#include <fstream>
using namespace std;
ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
struct info {
int s, st, dr, mx;
}aint[500000];
int v[100001];
void build(int nod, int ls, int rs) {
if (ls == rs) {
aint[nod].s = aint[nod].st = aint[nod].dr = aint[nod].mx = v[ls];
} else {
build(2 * nod + 1, ls, (ls + rs) / 2);
build(2 * nod + 2, (ls + rs) / 2 + 1, rs);
aint[nod].s = aint[2 * nod + 1].s + aint[2 * nod + 2].s;
aint[nod].st = max(aint[2 * nod + 1].st, aint[2 * nod + 1].s + aint[2 * nod + 2].st);
aint[nod].dr = max(aint[2 * nod + 2].dr, aint[2 * nod + 2].s + aint[2 * nod + 1].dr);
aint[nod].mx = max(max(aint[2 * nod + 1].mx, aint[2 * nod + 2].mx), aint[2 * nod + 1].dr + aint[2 * nod + 2].st);
}
}
info query(int nod, int st, int dr, int a, int b) {
info ans = {
0,
0,
0,
0
};
if (a <= st && dr <= b) {
return aint[nod];
} else {
int mid = (st + dr) / 2;
info ls, rs;
int ok1 = 0, ok2 = 0;
if (a <= mid) {
ls = query(2 * nod + 1, st, mid, a, b);
ok1 = 1;
}
if (b > mid) {
rs = query(2 * nod + 2, mid + 1, dr, a, b);
ok2 = 1;
}
if (ok1 == 1 && ok2 == 1) {
ans.s = rs.s + ls.s;
ans.st = max(ls.st, ls.s + rs.st);
ans.dr = max(rs.dr, rs.s + ls.dr);
ans.mx = max(max(ls.mx, rs.mx), ls.dr + ls.st);
} else if (ok1 == 1) {
ans = ls;
} else if (ok2 == 1) ans = rs;
return ans;
}
}
int main() {
int n, m, a, b;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i];
build(0, 1, n);
for (int i = 0; i < m; i++) {
cin >> a >> b;
info ans;
ans = query(0, 1, n, a, b);
cout << ans.mx << '\n';
}
}