#include <iostream>
#include <fstream>

using namespace std;

int N, M;
long long A[100001];
long long sum[300003], smax[300003], st[300003], dr[300003];

inline long long max(long long a, long long b)
{
	if (a > b)
		return a;
	return b;
}

inline long long min(long long a, long long b)
{
	if (a < b)
		return a;
	return b;
}

void build(int n, int l, int r)
{
	if (l == r) {
		sum[n] = smax[n] = st[n] = dr[n] = A[l];
		return;
	}
	int m = l + (r - l) / 2,
	    L = 2*n,
	    R = L + 1;

	build(L, l, m);
	build(R, m+1, r);

	sum[n] = sum[L] + sum[R];
	st[n] = max(st[L], sum[L] + st[R]);
	dr[n] = max(dr[R], sum[R] + dr[L]);
	smax[n] = max(sum[n], max(st[n], dr[n]));
	smax[n] = max(smax[n], dr[L] + st[R]);
	smax[n] = max(smax[n], max(smax[L], smax[R]));
}

long long sol, S;
void query(int n, int l, int r, int ql, int qr) 
{
	if ((l == ql) && (r == qr)) {
		sol = max(sol, S+st[n]);
		S = max(S+sum[n], dr[n]);
		sol = max(sol, smax[n]);
		sol = max(sol, S);

		return;
	}

	int m = l + (r - l) / 2,
	    L = 2*n,
	    R = L + 1;
	
	if (ql <= m)
		query(L, l, m, ql, min(qr, m));
	if (qr > m)
		query(R, m+1, r, max(ql, m+1), qr);
}

int main(int argc, char *argv[])
{
	FILE *fi = fopen("sequencequery.in", "r");
	fscanf(fi, "%d %d", &N, &M);
	for (int i(1); i <= N; ++i)
		fscanf(fi, "%lld", A+i);
	build(1, 1, N);

	int p, q;
	FILE *fo = fopen("sequencequery.out", "w");
	while (M--) {
		fscanf(fi, "%d %d", &p, &q);
		sol = S = -0x3f3f3f3f;
		query(1, 1, N, p, q);
		fprintf(fo, "%lld\n", sol);
	}
	fclose(fo);
	fclose(fi);

	return 0;
}