#include <fstream>
#define NMAX 100000
using namespace std;
ifstream cin ("sequencequery.in");
ofstream cout ("sequencequery.out");
struct straint {
int stotal, scmaxpref, scmaxsuf, scmax;
};
straint vaint[4 * NMAX + 1];
int v[NMAX + 1];
int maxim(int a, int b) {
return a > b ? a : b;
}
static inline int maxim(int a, int b, int c) {
return maxim(a, maxim(b, c));
}
static inline straint join(straint A, straint B) {
straint sol;
sol.stotal = A.stotal + B.stotal;
sol.scmax = maxim(A.scmax, B.scmax, A.scmaxsuf + B.scmaxpref);
sol.scmaxpref = maxim(A.scmaxpref, A.stotal + B.scmaxpref);
sol.scmaxsuf = maxim(B.scmaxsuf, B.stotal + A.scmaxsuf);
return sol;
}
void build(int node, int left, int right) {
if (left == right) {
vaint[node].scmax = vaint[node].scmaxsuf = vaint[node].scmaxpref = vaint[node].stotal = v[left];
return;
}
int mid = (left + right) / 2;
build(node * 2, left, mid);
build(node * 2 + 1, mid + 1, right);
vaint[node] = join(vaint[node * 2], vaint[node * 2 + 1]);
}
straint query(int node, int left, int right, int qleft, int qright) {
if (qleft <= left && qright >= right)
return vaint[node];
int mid = (left + right) / 2;
if (qleft <= mid && qright > mid)
return join(query(node * 2, left, mid, qleft, qright), query(node * 2 + 1, mid + 1, right, qleft, qright));
else if (qleft <= mid)
return query(node * 2, left, mid, qleft, qright);
else
return query(node * 2 + 1, mid + 1, right, qleft, qright);
}
int main() {
int n, q, i, a, b;
cin >> n >> q;
for (i = 0; i < n; i++)
cin >> v[i];
build(1, 0, n - 1);
while (q--) {
cin >> a >> b;
a--;
b--;
straint A = query(1, 0, n - 1, a, b);
cout << A.scmax << "\n";
}
return 0;
}