#include <cstdio>
#include <algorithm>
using namespace std;

#define ll long long

const int MAX_N = 100001;
const int INF = 0x3f3f3f3f;

struct aint{
	int max, tot, st, dr;
} a[MAX_N * 4];

int n, m;
int v[MAX_N];
ll s, sol;

void init(int nod, int st, int dr)
{
	if (st == dr)
	{
		a[nod].max = a[nod].tot = a[nod].st = a[nod].dr = v[st];

		return;
	}

	int mij = (st + dr) / 2;

	init(nod * 2, st, mij);
	init(nod * 2 + 1, mij + 1, dr);

	a[nod].max = max(max(a[nod * 2].max, a[nod * 2 + 1].max), a[nod * 2].dr + a[nod * 2 + 1].st);
	a[nod].tot = a[nod * 2].tot + a[nod * 2 + 1].tot;
	a[nod].st = max(a[nod * 2].st, a[nod * 2].tot + a[nod * 2 + 1].st);
	a[nod].dr = max(a[nod * 2 + 1].dr, a[nod * 2 + 1].tot + a[nod * 2].dr);
}

void query(int nod, int st, int dr, int l, int r)
{
	ll ret = 0;

	if (l <= st && dr <= r)
	{
		ret = a[nod].max;

		if (ret < s + a[nod].st)
			ret = s + a[nod].st;

		if (s + a[nod].tot > a[nod].dr)
			s += a[nod].tot;
		else
			s= a[nod].dr;

		if (sol < ret)
			sol = ret;

		return;
	}

	int mij = (st + dr) / 2;

	if (l <= mij)
		query(nod * 2, st, mij, l, r);
	if (mij < r)
		query(nod * 2 + 1, mij + 1, dr, l, r);
}

int main()
{
	int i;
	freopen("sequencequery.in", "r", stdin);
	freopen("sequencequery.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (i = 1; i <= n; ++i)
		scanf("%d", &v[i]);

	init(1, 1, n);

	for (i = 1; i <= m; ++i)
	{
		int x, y;

		scanf("%d %d", &x, &y);

		s = 0;
		sol = -INF;

		query(1, 1, n, x, y);

		printf("%lld\n", sol);
	}
}