#include <fstream>
#include <algorithm>

using namespace std;

fstream fin("sequencequery.in", ios::in);
fstream fout("sequencequery.out", ios::out);

#define MAXN 100005
struct node{
	long long max, l, r, sum;
} T[4 * MAXN + 10], *LS, *RS, S, *AC;
int N, M, pos, val, a, b;

void update(int node, int l, int r){
	if (l == r) { 
		T[node].max = T[node].l = T[node].r = T[node].sum = val;
		return;
	}
	int mid = (l + r) / 2;
	if (pos <= mid) update(node * 2, l, mid);
	else update(node * 2 + 1, mid + 1, r);

	LS = &T[node * 2], RS = &T[node * 2 + 1];
	T[node].max = max(max(LS->max, RS->max), LS->r + RS->l);
	T[node].sum = LS->sum + RS->sum;
	T[node].l = max(LS->sum + RS->l, LS->l);
	T[node].r = max(RS->sum + LS->r, RS->r);
}
void query(int node, int l, int r){
	if (a <= l && r <= b){
		S.max = max(max(S.max, T[node].max), S.r + T[node].l);
		S.r = max(T[node].r, max(S.r + T[node].sum, T[node].sum));
		return;
	}
	int mid = (l + r) / 2;
	if (a <= mid) query(node * 2, l, mid);
	if (b > mid) query(node * 2 + 1, mid + 1, r);
}

int main()
{
	S.max = S.r = ~(1 << 15);
	fin >> N >> M;
	for (int i = 1; i <= N; ++i) 
		fin >>val, pos = i, update(1, 1, N);
	for (int i = 1; i <= M; ++i)
		fin >> a >> b,
		query(1, 1, N),
		fout << S.max << "\n",
		S.max = S.r = ~(1 << 15);

	fin.close();
	fout.close();
	return 0;
}