#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 100000;

typedef long long ll;

ll n, m, ma, s;

ll v[NMAX + 1];
ll AintS[4 * NMAX]; /// suma pe intervalul lui nod
ll AintL[4 * NMAX];// -subsecventa de suma maxima care incepe din st lui nod si se termina tot in intervalul lui
ll AintR[4 * NMAX];// -subsecventa de suma maxima care se termina pe dr lui nod
ll AintM[4 * NMAX]; //-subscventa de suma maxima din intervalul lui nod


void build(int nod, int l, int r) {
	if (l == r) {
		AintL[nod] = AintR[nod] = AintM[nod] = AintS[nod] = v[l];
		return;
	}
	int mj = (l + r) / 2;
	build(nod * 2, l, mj);
	build(nod * 2 + 1, mj + 1, r);
	AintS[nod] = AintS[nod * 2] + AintS[nod * 2 + 1];
	AintM[nod] = max(AintR[nod * 2] + AintL[nod * 2 + 1], max(AintM[nod * 2], AintM[nod * 2 + 1]));
	AintL[nod] = max(AintL[nod * 2], AintS[nod * 2] + AintL[nod * 2 + 1]);
	AintR[nod] = max(AintR[nod * 2 + 1], AintS[nod * 2 + 1] + AintR[nod * 2]);

}
/*
void Update(long long nod, long long le, long long ri, long long poz, long long val) {

	if (le == ri) {
		AintL[nod] = AintR[nod] = AintM[nod] = AintS[nod] = val;
		return;
	}

	long long mj = (le + ri) / 2;
	if (mj >= poz)
		Update(nod * 2, le, mj, poz, val);
	else
		Update(nod * 2 + 1, mj + 1, ri, poz, val);
	AintS[nod] = AintS[nod * 2] + AintS[nod * 2 + 1];
	AintM[nod] = max(AintR[nod * 2] + AintL[nod * 2 + 1], max(AintM[nod * 2], AintM[nod * 2 + 1]));
	AintL[nod] = max(AintL[nod * 2], AintS[nod * 2] + AintL[nod * 2 + 1]);
	AintR[nod] = max(AintR[nod * 2 + 1], AintS[nod * 2 + 1] + AintR[nod * 2]);
}*/


void Query(long long nod, long long le, long long ri, long long x, long long y) {

	if (x <= le and ri <= y) {

		ma = max(ma, AintM[nod]);
		ma = max(ma, s + AintL[nod]);
		s = max(s + AintS[nod], AintR[nod]);

		return;
	}

	long long mj = (le + ri) / 2;
	if (x <= mj)
		Query(nod * 2, le, mj, x, y);
	if (y >= mj + 1)
		Query(nod * 2 + 1, mj + 1, ri, x, y);
}


int main() {

	int x, y, type;
	fin >> n >> m;
	for (int i = 1; i <= n; ++i)
		fin >> v[i];// Update(1, 1, n, i, v[i]);

	build(1, 1, n);

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

		ma = s = -100000000;

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

		fout << ma << "\n";
	}

}