#include <iostream>
#include <fstream>
#define maxn 100005

using namespace std;

const char iname[] = "sequencequery.in";
const char oname[] = "sequencequery.out";

ifstream fin(iname);
ofstream fout(oname);

int A[maxn], Sum[3 * maxn], Sol[3 * maxn], Left[3 * maxn], Right[3 * maxn], S, N;
int i, j, k, M, a, b, solution;

void build(int n, int left, int right)
{
	if(left == right)
	{
		Sum[n] = Sol[n] = Left[n] = Right[n] = A[left];
		return;
	}
	int middle = (left + right) >> 1;
	build(2 * n, left, middle);
	build(2 * n + 1, middle + 1, right);
	
	Sum[n] = Sum[2 * n] + Sum[2 * n + 1];
	Left[n] = max(Left[2 * n], Sum[2 * n] + Left[2 * n + 1]);
	Right[n] = max(Right[2 * n + 1], Sum[2 * n + 1] + Right[2 * n]);
	Sol[n] = max(Sol[n], max(Right[n], Left[n]));
	Sol[n] = max(Sol[n], Right[2 * n] + Left[2 * n + 1]);
	Sol[n] = max(Sol[2 * n], Sol[2 * n + 1]);
}
	
void query(int n, int left, int right)
{
	if(a <= left && right <= b)
	{
		solution = max(solution, S + Left[n]);
		S = max(S + Sum[n], Right[n]);
		solution = max(solution, S);
		solution = max(solution, Sol[n]);
		solution = max(solution, Left[n]);
		return;
	}
	else
	{
		int middle = (left + right) >> 1;
		if(a <= middle)
			query(2 * n, left, middle);
		if(b > middle)
			query(2 * n + 1, middle + 1, right);
	}
			
}

int main()
{
	fin >> N >> M;
	for(i = 1; i <= N; i ++)
		fin >> A[i];
	build(1, 1, N);
	for(i = 1; i <= M; i ++)
	{
		fin >> a >> b;
		solution = -241894981;
		S = - 24189498;
		query(1, 1, N);
		fout << solution << "\n";
	}
	return 0;
}