#include <fstream>
#include <algorithm>

using namespace std;

struct Node
{
	long long s1, s2, s3;
	long long tot;
};

const int INF = 0x3f3f3f3f;

Node AI[4 * 100001];
int N, M;
int V[100001];
long long result, auxr;

void Update(int nod, int s1, int s2)
{
	if (s1 == s2)
	{
		AI[nod].s1 = AI[nod].s2 = AI[nod].s3 = AI[nod].tot = V[s1];
		return;
	}

	int med = (s1 + s2) / 2;
	Update(nod * 2, s1, med);
	Update(nod * 2 + 1, med + 1, s2);

	AI[nod].tot = AI[nod * 2].tot + AI[nod * 2 + 1].tot;

	AI[nod].s1 = max(AI[nod * 2].s1, AI[nod * 2].tot + AI[nod * 2 + 1].s1);
	AI[nod].s2 = max(AI[nod * 2 + 1].s2, AI[nod * 2 + 1].tot + AI[nod * 2].s2);

	AI[nod].s3 = max(AI[nod].s1, AI[nod].s2);
	AI[nod].s3 = max(AI[nod].s3, AI[nod * 2].s3);
	AI[nod].s3 = max(AI[nod].s3, AI[nod * 2 + 1].s3);
	AI[nod].s3 = max(AI[nod].s3, AI[nod * 2].s2 + AI[nod * 2 + 1].s1);
}
void Query(int nod, int s1, int s2, int a, int b)
{
	if (a <= s1 && s2 <= b)
	{
		result = max(result, AI[nod].s3);
		result = max(result, auxr + AI[nod].s1);

		auxr = max(auxr + AI[nod].tot, AI[nod].s2);
		auxr = max(auxr, 0LL);

		return;
	}

	int md = (s1 + s2) / 2;
	if (a <= md) Query(nod * 2, s1, md, a, b);
	if (b > md)  Query(nod * 2 + 1, md + 1, s2, a, b);
}

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

	fin >> N >> M;
	for (int i = 1; i <= N; ++i)
		fin >> V[i];
	Update(1, 1, N);
	for (int i = 1, pos1, pos2; i <= M; ++i)
	{
		fin >> pos1 >> pos2;

		result = -INF, auxr = -INF;
		Query(1, 1, N, pos1, pos2);


		fout << result << '\n';
	}

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