#include <fstream>
#define  NMAX 100000
#define int long long

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);
}

signed 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;
}