#include <cstdio>

const int NMAX = 1 << 17;
const int MMAX = 1 << 18;

int N, M, a, b;
int V[NMAX];
long long A[MMAX], B[MMAX], C[MMAX], D[MMAX];
long long S, rez;

/*
 * A[] suma tuturor elem din st - dr
 * B[] suma secventei maxime
 * C[] suma maxima din stanga
 * D[] suma maxima din dreapta
 */

template <typename T> T max(T a, T b) { return a > b ? a : b; }

void construct(int i, int st, int dr) {
	if (st == dr) {
		A[i] = B[i] = C[i] = D[i] = V[st];
	} else {
		int mij, is, j;
		long long s;

		mij = (st + dr) >> 1;
		is = i << 1;

		construct(is, st, mij);
		construct(is | 1, mij + 1, dr);

		A[i] = A[is] + A[is | 1];
		B[i] = C[i] = V[st];
		D[i] = V[dr];
	
		for (j = st, s = 0; j <= dr; ++j) {
			s += V[j];
			if (s > B[i]) B[i] = s;
			if (s < 0) s = 0;
		}

		for (j = st, s = 0; j <= dr; ++j)
			C[i] >?= s += V[j];

		for (j = dr, s = 0; j >= st; --j)
			D[i] >?= s += V[j];
	}
}

void query(int i, int st, int dr) {
	if (a <= st && dr <= b) {
		rez >?= max(S + C[i], B[i]);
		S = max(S + A[i], D[i]);
	} else {
		int mij, is;

		mij = (st + dr) >> 1;
		is = i << 1;
		if (a <= mij) query(is, st, mij);
		if (mij < b) query(is | 1, mij + 1, dr);
	}
}

int main(void) {
	FILE *fin = fopen("sequencequery.in", "rt");
	FILE *fout = fopen("sequencequery.out", "wt");
	int i;

	fscanf(fin, " %d %d", &N, &M);

	for (i = 1; i <= N; ++i)
		fscanf(fin, " %d", V + i);
	
	construct(1, 1, N);

	for (i = 0; i < M; ++i) {
		fscanf(fin, " %d %d", &a, &b);

		rez = V[a]; S = 0; query(1, 1, N);
		fprintf(fout, "%lld\n", rez);
	}

	fclose(fin);
	fclose(fout);

	return 0;
}