#include <fstream>
#include <algorithm>
using namespace std;
struct node{
	long l, r, m, s;
};

ifstream f("sequencequery.in");
ofstream of("sequencequery.out");
int N, M, a, b, pos, val, c, A[100001], start, finish;
node ARB[400020];
void add(node&nod, const node&l, const node&r){
	nod.s = l.s + r.s;
	nod.l = max(l.l, l.s + r.l);
	nod.r = max(r.r, r.s + l.r);
	nod.m = max(nod.l, max(nod.r, max(l.m, max(r.m, l.r + r.l))));
}
void assi(const int&i, const int&v){
	ARB[i].m = ARB[i].l = ARB[i].r = ARB[i].s = v;
}
void bt(const int& nod, const int& l, const int& h){
	if (l == h){
		assi(nod, A[l]);
		return;
	}
	int m = (l + h) >> 1;
	bt(nod << 1, l, m);
	bt((nod << 1) + 1, m + 1, h);
	add(ARB[nod], ARB[nod << 1], ARB[(nod << 1) + 1]);
}
void update(const int&nod, const int&l, const int&h){
	if (l == h){
		assi(nod, val);
		return;
	}
	int m = (l + h) >> 1;
	if (pos <= m)update(nod << 1, l, m);
	else update((nod << 1) + 1, m + 1, h);
	add(ARB[nod], ARB[nod << 1], ARB[(nod << 1) + 1]);
}
node q(const int& nod, const int&left, const int&right, const int& start, const int&finish){
	if (left == start && right == finish){
		return ARB[nod];
	}
	int m = (left + right) >> 1;
	if (start > m)return q((nod << 1) + 1, m + 1, right, start, finish);
	if (finish <= m)return q(nod << 1, left, m, start, finish);
	node result;
	add(result, q((nod << 1), left, m, start, m), q((nod << 1) + 1, m + 1, right, m + 1, finish));
	return result;
}
int main(){
	f >> N >> M;
	for (int i = 0; i < N; ++i)f >> A[i];
	bt(1, 0, N - 1);
	for (int i = 0; i < M; ++i){
		f >> a >> b;
		of<< q(1, 0, N - 1, a-1, b-1).m<<"\n";
	}
}