#include <bits/stdc++.h>

using ll = long long;
using namespace std;

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

const ll kInf = 1e15;

void maxSelf(int &x, int y) {
	if(y > x) {
		x = y;
	}
}

void maxSelf(ll &x, ll y) {
	if(y > x) {
		x = y;
	}
}

struct st {
	struct Node {
		ll sum, pref, suff, ssmax;
		Node(ll sum = 0, ll pref = 0, ll suff = 0, ll ssmax = 0): sum(sum), pref(pref), suff(suff), ssmax(ssmax) {}
	};
	friend Node operator + (const Node &l, const Node &r) {
		Node res(l.sum + r.sum, max(l.pref, l.sum + r.pref), max(r.suff, r.sum + l.suff), l.sum + r.sum);
		maxSelf(res.ssmax, l.ssmax);
		maxSelf(res.ssmax, r.ssmax);
		maxSelf(res.ssmax, l.suff + r.pref);
		maxSelf(res.ssmax, res.pref);
		maxSelf(res.ssmax, res.suff);
		return res;
	}
	vector<Node> segTree;
	vector<int> v;
	st() {}
	st(const vector<int> &v): v(v) {
		segTree = vector<Node>(4 * v.size() + 1);
		build(1, 0, v.size() - 1);
	}
	void build(int node, int l, int r) {
		if(l == r) {
			segTree[node] = Node(v[l], v[l], v[l], v[l]);
		} else {
			int m = (l + r) >> 1;
			build(node << 1, l, m);
			build(node << 1 | 1, m + 1, r);
			segTree[node] = segTree[node << 1] + segTree[node << 1 | 1];
		}
	}
	Node query(int a, int b, int node, int l, int r) {
		if(a <= l && r <= b) {
			return segTree[node];
		} else {
			int m = (l + r) >> 1;
			Node res(0, -kInf, -kInf, -kInf);
			if(a <= m) {
				res = res + query(a, b, node << 1, l, m);
			}
			if(b > m) {
				res = res + query(a, b, node << 1 | 1, m + 1, r);
			}
			return res;
		}
	}
};

int main() {
	int n, q;
	fin >> n >> q;
	vector<int> v(n);
	for(auto &it: v) {
		fin >> it;
	}
	st ds(v);
	for(int i = 0; i < q; i++) {
		int a, b;
		fin >> a >> b;
		a--; b--;
		fout << ds.query(a, b, 1, 0, n - 1).ssmax << '\n';
	}
	return 0;
}