#include <fstream>
using namespace std;
struct elem {
	long long secv, pre, suf, tot;
};
elem v[263000];
elem fusion(elem a, elem b) {
	elem r;
	if (a.secv == -INT32_MAX) {
		return b;
	}
	if (b.secv == -INT32_MAX) {
		return a;
	}
	r.secv = max( a.suf + b.pre, max( a.secv, b.secv ) );
	r.pre = max( a.pre, a.tot + b.pre );
	r.suf = max( b.suf, b.tot + a.suf );
	r.tot = a.tot + b.tot;
	return r;
}
void modif(int nod, int st, int dr, int x, int val) {
	int mij = ( st + dr ) / 2;
	if (st == x && dr == x) {
		v[nod].secv = v[nod].pre = v[nod].suf = v[nod].tot = val;
	}
	else {
		if (x <= mij) {
			modif( nod * 2, st, mij, x, val );
		}
		else {
			modif( nod * 2 + 1, mij + 1, dr, x, val );
		}
		v[nod] = fusion( v[nod * 2], v[nod * 2 + 1] );
	}
}
elem sum(int nod, int st, int dr, int x, int y) {
	int mij = ( st + dr ) / 2;
	elem r;
	if (x <= st && dr <= y) {
		return v[nod];
	}
	r.secv = -INT32_MAX;
	if (x <= mij) {
		r = fusion( r, sum( nod * 2, st, mij, x, y ) );
	}
	if (y > mij) {
		r = fusion( r, sum( nod * 2 + 1, mij + 1, dr, x, y ) );
	}
	return r;
}
int main() {
	int n, m, i, x, y;
	ifstream fin( "sequencequery.in" );
	ofstream fout( "sequencequery.out" );
	fin >> n >> m;
	for (i = 0; i < n; i++) {
		fin >> x;
		modif( 1, 0, n - 1, i, x );
	}
	for (i = 0; i < m; i++) {
		fin >> x >> y;
		fout << sum( 1, 0, n - 1, x - 1, y - 1 ).secv << '\n';
	}
	return 0;
}