//https://kilonova.ro/problems/304
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
typedef long long ll;
const ll N = 100005;
const ll INF = 1e5 + 27;


struct node {
	ll maxpref, maxsuf, best, sum;
};

ll n, m;
ll minpref;
vector<ll>v(N),sume(N);
node arb[N * 4];


void update(ll nod, ll st, ll dr, ll poz, ll val)
{
	if (st == dr) {
			arb[nod].maxpref = v[st];
			arb[nod].maxsuf = v[st];
			arb[nod].best = v[st];
			arb[nod].sum = v[st];
		}
	else {
		ll mij = (st + dr) / 2;
		if (poz <= mij)
			update(nod * 2, st, mij, poz, val);
		if (poz > mij)
			update(2 * nod + 1, mij + 1, dr, poz, val);

		arb[nod].sum = arb[2 * nod].sum + arb[2 * nod + 1].sum;
		arb[nod].maxpref = max(arb[2 * nod].maxpref, arb[2 * nod].sum + arb[2 * nod + 1].maxpref);
		arb[nod].maxsuf = max(arb[2 * nod + 1].maxsuf, arb[2 * nod].maxsuf + arb[2 * nod + 1].sum);
		arb[nod].best = max({ arb[2 * nod].best,
			arb[2 * nod + 1].best,
			arb[2 * nod].maxsuf + arb[2 * nod + 1].maxpref });
	}
			
}

ll maxsum, prefix;

void query(ll nod, ll st, ll dr,ll qst, ll qdr) {
	if (qst <= st && dr <= qdr)
	{
		maxsum = max(arb[nod].best,maxsum);
		maxsum = max(maxsum, prefix + arb[nod].maxpref);
		prefix = max(prefix + arb[nod].sum, arb[nod].maxsuf);
	}
	else
	{
		ll mij = (st + dr) / 2;
		if (qst <= mij)
			 query(2 * nod, st, mij, qst, qdr);
		if (qdr > mij)
			 query(2 * nod + 1, mij + 1, dr, qst, qdr);
	}
}

int main() {
	f >> n >> m;
	for (ll i = 1; i <= n; i++)
	{
		f >> v[i];
		update(1, 1, n, i, v[i]);
	}
	/*for (int i = 1; i <= 4 * n; i++)
		cout << i << ": " << arb[i].maxpref << " " << arb[i].maxsuf << " " << arb[i].best << "\n";
	*/
	while (m--) {
		ll a, b;
		f >> a >> b;
		maxsum =- INF;
		prefix = 0;
		query(1, 1, n, a, b);
		g << maxsum << "\n";

	}
}