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

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

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

		A[i] = A[is] + A[id];
		B[i] = max( max(B[is], B[id]), D[is] + C[id]);
		C[i] = max(C[is], A[is] + C[id]);
		D[i] = max(D[id], A[id] + D[is]);
	}
}

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