#include <fstream>
using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

#define INF 0x3f3f3f3f
#define LL long long
#define NMAX 100001
#define L (n << 1)
#define R (L | 1)

int i, j, N, M;
LL best, sum;
int x, y;

int v[NMAX];
LL Ans[3 * NMAX];
LL Sum[3 * NMAX];
LL Left[3 * NMAX];
LL Right[3 * NMAX];

inline void build(int n, int l, int r) {
	if (l == r){
		Sum[n] = Left[n] = Right[n] = v[l];
		Ans[n] = v[l];
		return;
	}
	int m = (l + r) >> 1;
	build(L, l, m);
	build(R, m + 1, r);
	Sum[n] = Sum[L] + Sum[R];
	Left[n] = max(Left[L], Sum[L] + Left[R]);
	Right[n] = max(Right[R], Sum[R] + Right[L]);
	Ans[n] = max(max(Ans[L], Ans[R]), Right[L] + Left[R]);
}

inline void query(int n, int l, int r, int i, int j) {
	if (i <= l && r <= j) {
		best = max(best, max(sum + Left[n], Ans[n]));
		sum = max(sum + Sum[n], Right[n]);
		return;
	}
	int m = (l + r) >> 1;
	if (i <= m) query(L, l, m, i, j);
	if (j > m) query(R, m + 1, r, i, j);
}

int main() {
	fin >> N >> M;
	for (i = 1; i <= N; ++i) fin >> v[i];
	build(1, 1, N);
	while (M--) {
		sum = best = -INF;
		fin >> x >> y;
		query(1, 1, N, x, y);
		fout << best << '\n';
	}
	return 0;
}