#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//int d1[5] = { 0, -1, 0, 1, 0 };
//int d2[5] = { 0, 0, 1, 0, -1 };

//int d11[9] = { 0 , -1, -1, 0, 1, 1, 1, 0, -1 };
//int d22[9] = { 0, 0, 1, 1, 1, 0, -1, -1, -1 };
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");


//----------------------------------

ll n, q, v[100001];

int kadane(int l, int r) {

	int ans = INT_MIN, sum = 0;
	vector<int> dp(n + 1);
	for (int i = l; i <= r; i++) {
		dp[i] = max(dp[i - 1], 0) + v[i];
		ans = max(ans, dp[i]);
	}
	return ans;
}
struct lmao {
	ll sum, prefix = INT_MIN, sufix = INT_MIN, max = INT_MIN;
} t[300001];

lmao createD(int val) {
	lmao req;
	req.sum = val;
	req.prefix = req.sufix = req.max = max(val, 0);

	return req;
}

lmao compress(lmao a, lmao b) {

	lmao res;
	res.sum = a.sum + b.sum;
	res.prefix = max(a.prefix, a.sum + b.prefix);
	res.sufix = max(b.sufix, b.sum + a.sufix);
	res.max = max(max(a.max, b.max), a.sufix + b.prefix);

	return res;
}
void build(ll a[], int v, int tl, int tr) {

	if (tl == tr) t[v] = createD(a[tl]);
	else {
		int tm = (tl + tr) / 2;
		build(a, v * 2, tl, tm);
		build(a, v * 2 + 1, tm + 1, tr);

		t[v] = compress(t[v * 2], t[v * 2 + 1]);
	}
}

lmao query(int v, int tl, int tr, int l, int r) {

	if (l <= tl && r >= tr) return t[v];
	if (tr < l || tl > r) return createD(0);

	int tm = (tl + tr) / 2;
	lmao ans1 = query(v * 2, tl, tm, l, r);
	lmao ans2 = query(v * 2 + 1, tm + 1, tr, l, r);

	return compress(ans1, ans2);
}
int main() {

	fin >> n >> q;
	for (int i = 1; i <= n; i++) {
		fin >> v[i];
	}

	build(v, 1, 1, n);

	while (q--) {
		int l, r;
		fin >> l >> r;
		lmao ans = query(1, 1, n, l, r);
		if (ans.max == 0) {
			fout << kadane(l, r) << '\n';
		}
		else fout << ans.max << '\n';
	}

}