#include <cstdio>

using namespace std;

const char iname[] = "sequencequery.in";
const char oname[] = "sequencequery.out";

#define MAX_N 100001

typedef long long LL;

LL  M[MAX_N * 3];

LL  L[MAX_N * 3];

LL  R[MAX_N * 3];

int A[MAX_N];

LL  S[MAX_N];


#define mid   ((l + r) >> 1)
#define left  (2 * n)
#define right (2 * n + 1)

void build_tree(int n, int l, int r)
{
	if (l == r) {
		M[n] = L[n] = R[n] = (LL)A[l];
		return ;
	}
	build_tree(left, l, mid);
	build_tree(right, mid+1, r);
	
	/* actualizez informatia din nod */
	M[n] = (M[left] > M[right]) ? M[left] : M[right];
	if (M[n] < R[left] + L[right])
		M[n] = R[left] + L[right];

	L[n] = S[mid] - S[l-1] + L[right];
	if (L[n] < L[left])
		L[n] = L[left];

	R[n] = S[r] - S[mid] + R[left];
	if (R[n] < R[right])
		R[n] = R[right];
}

int X, Y;

LL  SUM, MAX;

void query(int n, int l, int r)
{
	if (X <= l && r <= Y) {
		if (MAX < ((M[n] > SUM + L[n]) ? M[n] : (SUM + L[n])))
			MAX = ((M[n] > SUM + L[n]) ? M[n] : (SUM + L[n]));
		if (SUM +  S[r] - S[l-1] > R[n])
			SUM += S[r] - S[l-1];
		else
			SUM  = R[n];
		return;
	}
	if (X <= mid)
		query(left, l, mid);
	if (Y >  mid)
		query(right, mid+1, r);
}

int main(void)
{
	freopen(iname, "r", stdin);
	freopen(oname, "w", stdout);
	int N, I;
	int i;

	for (scanf("%d %d", &N, &I), i = 1; i <= N; ++i)
		scanf("%d", A + i), S[i] = S[i-1] + (LL)A[i];

	build_tree(1, 1, N);

	for (i = 1; i <= I; ++i) {
		scanf("%d %d", &X, &Y);
		SUM = 0;
		MAX = - int(1e11);
		query(1, 1, N);
		printf("%lld\n", MAX);
	}

	return 0;
}