#include <cstdio>

using namespace std;

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

#define MAX_N   100001
#define MAX_BUF 4000000

#define isnum(z) ('0' <= (z) && (z) <= '9')

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];

char buffer[MAX_BUF];


#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;

	scanf("%d %d", &N, &I);

	int sign;
	int len = fread(buffer, sizeof(char), MAX_BUF, stdin);
	char *p = buffer;
	char *lim = buffer + len;

	for (i = 1; i <= N; ++i) {
		for (; p < lim && *p != '-' && !isnum(*p); ++p) ;
		sign = *p == '-' ? -1 : +1;
		if (*p == '-')
			++p;
		for (; p < lim && isnum(*p); ++p)
			A[i] = A[i] * 10 + (*p) - '0';
		A[i] *= sign;
		S[i] = S[i - 1] + (LL)(A[i]);
	}

	build_tree(1, 1, N);

	for (i = 1; i <= I; ++i) {
		X = Y = 0;
		for (; p < lim && *p <  '0'; ++p) ;
		for (; p < lim && *p >= '0'; ++p)
			X = X * 10 + (*p) - '0';
		for (; p < lim && *p <  '0'; ++p) ;
		for (; p < lim && *p >= '0'; ++p)
			Y = Y * 10 + (*p) - '0';
		SUM = 0;
		MAX = - int(1e11);
		query(1, 1, N);
		printf("%lld\n", MAX);
	}

	return 0;
}