#include<stdio.h>

#define MAX (1<<19)

int N, M, v[MAX];
long long int A[MAX], B[MAX], C[MAX], D[MAX];
long long int S, rez;

long long int max(long long int x, long long int y) { return x > y ? x : y;}

void build(int nod, int left, int right)
{
	int middle, l, r;
	if (left == right)
	{
		A[nod] = B[nod] = C[nod] = D[nod] = v[left];
	}
	else
	{
		middle = (left + right) / 2;
		l = 2 * nod; r = l + 1;
		build(l, left, middle);
		build(r, middle + 1, right);

		A[nod] = max(A[l], D[l] + A[r]);
		B[nod] = max(D[r] + B[l], B[r]);
		C[nod] = max(max(C[l],C[r]), A[r] + B[l]);

		D[nod] = D[l] + D[r];
	}
}

void query(int nod, int left, int right, int st, int dr)
{
	int l, r, middle;
	if (st <= left && right <= dr)
	{
		if (S < 0) S = 0;
		rez = max(rez, max(S + A[nod], C[nod]));
		S = max(S + D[nod], B[nod]);
	}
	else
	{
		l = nod * 2; r = l + 1;
		middle = (left + right) / 2;
		if (st <= middle) query(l, left, middle, st, dr);
		if (dr > middle) query(r, middle + 1, right, st, dr);
	}
}

int main()
{
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);

	int i, x, y;
	scanf("%d %d", &N, &M);
	for (i = 1; i <= N; i++) scanf("%d",&v[i]);
	build(1,1,N);
	
	for (i = 1; i <= M; i++)
	{
		scanf("%d %d",&x, &y);
	
	//	x++; y++;
		S = 0; rez = v[x];
		query(1, 1, N, x, y);
	//	if (rez < 0) rez = 0;
		printf("%lld\n",rez);
	
	}
	return 0;
}