#include <cstdio>
#define DIM (1 << 18)
#define pivot ((st + dr) >> 1)
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;

int N, M, X, Y;
long long V[DIM], A[DIM << 1], B[DIM << 1], C[DIM << 1], S[DIM << 1], sum, sol;

void Build(int nod, int st, int dr)
{
	if (st == dr)
	{
		A[nod] = B[nod] = C[nod] = S[nod] = V[st];
		return;
	}
	Build(2 * nod, st, pivot);
	Build(2 * nod + 1, pivot + 1, dr);
	A[nod] = max(A[2 * nod], A[2 * nod + 1] + S[2 * nod]);
	B[nod] = max(B[2 * nod + 1], S[2 * nod + 1] + B[2 * nod]);
	C[nod] = max(max (C[2 * nod], C[2 * nod + 1]), A[2 * nod + 1] + B[2 * nod]);
	S[nod] = S[2 * nod] + S[2 * nod + 1];
}

void Query(int nod, int st, int dr)
{
	if (X <= st && dr <= Y)
	{
		sol = max(sol, max(sum + A[nod], C[nod]));
		sum = max(sum + S[nod], B[nod]);
		return;
	}
	if (X <= pivot) Query(2 * nod, st, pivot);
	if (Y >  pivot) Query(2 * nod + 1, pivot + 1, dr);
}

int main()
{
	FILE *fin = fopen("sequencequery.in", "r");
	FILE *fout = fopen("sequencequery.out", "w");

	fscanf(fin, "%d%d", &N, &M);
	for (int i = 1; i <= N; i++)
		fscanf(fin, "%lld", V + i);
	Build(1, 1, N);
	for (int i = 1; i <= M; i++)
	{
		fscanf(fin, "%d%d", &X, &Y);
		sum = 0;
		sol = -9999999;
		Query(1, 1, N);
		fprintf(fout, "%lld\n", sol);
	}

	fclose(fin);
	fclose(fout);
	return 0;
}