#include <iostream>
#include <fstream>
#include <algorithm>
#define fs(i) i << 1
#define fd(i) (i << 1) + 1
#define maxN 100005 * 4

using namespace std;

struct nod{
	long long r, pref, suf, s;
} A[maxN];


void update(int l, int r, int i, int p, int v){
	if (l == r){
		A[i].pref = A[i].suf = A[i].r = A[i].s = v;
		return;
	}

	int m = (l + r) >> 1;
	if (p <= m)
		update(l, m, fs(i), p, v);
	else
		update(m + 1, r, fd(i), p, v);

	A[i].r = max(max(A[fs(i)].r, A[fd(i)].r), A[fs(i)].suf + A[fd(i)].pref);
	A[i].pref = max(A[fs(i)].pref, A[fs(i)].s + A[fd(i)].pref);
	A[i].suf = max(A[fd(i)].suf, A[fd(i)].s + A[fs(i)].suf);
	A[i].s = A[fs(i)].s + A[fd(i)].s;
}

nod vezi(int l, int r, int a, int b, int i){
	if (l >= a && r <= b)
		return A[i];

	int m = (l + r) >> 1;
	nod v1, v2, v3;
	v1.r = v1.pref = v1.suf = v1.s = -500000;
	v2.r = v2.pref = v2.suf = v2.s = -500000;
	if (a <= m) v1 = vezi(l, m, a, b, fs(i));
	if (b > m) v2 = vezi(m + 1, r, a, b, fd(i));

	v3.r = max(max(v1.r, v2.r), v1.suf + v2.pref);
	v3.pref = max(v1.pref, v1.s + v2.pref);
	v3.suf = max(v2.suf, v2.s + v1.suf);
	v3.s = v1.s + v2.s;
	return v3;
}

int main(){
	ifstream f("sequencequery.in");
	ofstream g("sequencequery.out");

	int n, m;

	f >> n >> m;

	for (int i = 1; i <= n; ++i){
		int x;
		f >> x;
		update(1, n, 1, i, x);
	}

	for (int i = 0; i < m; ++i){
		int x, y;
		nod d;
		f >> x >> y;
		d = vezi(1, n, x, y, 1);
		g << d.r << "\n";
	}

	f.close();
	g.close();

	return 0;
}