//arbori de intervale -> 100p

#include <cstdio>
#include <algorithm>
using namespace std;

#define FIN "maxq.in"
#define FOUT "maxq.out"

#define MAX_N (1<<18)
#define max(a, b) ((a) > (b) ? (a) : (b))

int N, M;
int v[MAX_N];
long long A[MAX_N<<1], B[MAX_N<<1], C[MAX_N<<1], Sum[MAX_N<<1];

#define lf (n<<1)
#define rt (lf+1)
#define md ((l+r)>>1)

void build(int n, int l, int r)
{
	if (l == r) {
		A[n] = B[n] = C[n] = max(v[l], 0);
		Sum[n] = v[l];
	} else {
		build(lf, l, md);
		build(rt, md+1, r);

		A[n] = max(A[lf], Sum[lf]+A[rt]);
		B[n] = max(B[lf]+Sum[rt], B[rt]);
		C[n] = max(max(C[lf], C[rt]), B[lf]+A[rt]);
		
		Sum[n] = Sum[lf]+Sum[rt];
	}
}

int a, b;
long long ans, S;

void query(int n, int l, int r) // a, b
{
	if (a <= l && r <= b) {
		if (S < 0) S = 0;
		ans = max(ans, max(S+A[n], C[n]));
		S = max(S+Sum[n], B[n]);
	} else {
		if (a <= md) query(lf,    l, md);
		if (b >  md) query(rt, md+1,  r);
	}
}

int main()
{
	int i, t, v1, v2;
	
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);

	scanf("%d %d", &N, &M);
	for (i = 1; i <= N; ++i)
		scanf("%d", v+i);
	build(1, 1, N);
	while (M--) {
		scanf("%d %d %d", &v1, &v2);
		// query
			S = ans = 0;
			a = v1;
			b = v2;
			query(1, 1, N);

			printf("%lld\n", ans);
		
	}
	return 0;
}