#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 100005
#define INF 1 << 61

struct inter {
	long long a, b, c, s;
} c;

int n, m, a, b, x, i;
long long A[4 * NMAX], B[4 * NMAX], C[4 * NMAX], S[4 * NMAX];

inter query (int, int, int, int, int);
void update (int, int, int, int, int);

int main () {
	
	freopen ("sequencequery.in", "r", stdin);
	freopen ("sequencequery.out", "w", stdout);
	
	scanf ("%d %d", &n, &m);
	
	for (i = 1; i <= 2 * n; i++)
		A[i] = B[i] = C[i] = -INF;
	
	for (i = 1; i <= n; i++) {
		scanf ("%d", &x);
		update (1, 1, n, i, x);
	}
	
	for (i = 1; i <= m; i++) {
		scanf ("%d %d", &a, &b);
		c = query (1, 1, n, a, b);
		printf ("%lld\n", max (c.a, max (c.b, c.c)));
	}
	
	return 0;
}

void update (int nod, int st, int dr, int poz, int x) {
	
	int mij = (st + dr) >> 1;
	
	if (st == dr) {
		A[nod] = B[nod] = C[nod] = S[nod] = x;
		return;
	}
	
	if (poz <= mij)
		update (2 * nod, st, mij, poz, x);
	else
		update (2 * nod + 1, mij + 1, dr, poz, x);
	
	A[nod] = max (A[2 * nod], max (A[2 * nod + 1], C[2 * nod] + B[2 * nod + 1]));
	B[nod] = max (B[2 * nod], B[2 * nod + 1] + S[2 * nod]);
	C[nod] = max (C[2 * nod + 1], C[2 * nod] + S[2 * nod + 1]);
	S[nod] = S[2 * nod] + S[2 * nod + 1];
}

inter query (int nod, int st, int dr, int a, int b) {
	
	int mij = (st + dr) >> 1;
	inter x, y, z;
	
	if (a <= st && dr <= b) {
		z.a = A[nod], z.b = B[nod], z.c = C[nod], z.s = S[nod];
		return z;
	}
	
	x.a = x.b = x.c = x.s = -INF, y.a = y.b = y.c = y.s = -INF;
	
	if (a <= mij)
		x = query (2 * nod, st, mij, a, b);
	if (b > mij)
		y = query (2 * nod + 1, mij + 1, dr, a, b);
	
	z.a = max (x.a, max (y.a, y.b + x.c));
	z.b = max (x.b, y.b + x.s);
	z.c = max (y.c, x.c + y.s);
	z.s = x.s + y.s;
	
	return z;
}