#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fi("sequencequery.in");
ofstream fo("sequencequery.out");


#define LL long long
typedef vector<int> VI;
typedef VI::iterator IT;

VI v;

LL SMax(IT a, IT b);

int main()
{
	LL n, k, i, a, b;
	fi >> n >> k;
	for (i = 0; i < n; i++)
	{
		fi >> a;
		v.push_back(a);
	}
	for (i = 1; i <= k; i++)
	{
		fi >> a >> b;
		fo << SMax(v.begin() + a - 1, v.begin() + b - 1) << "\n";
	}
	return 0;
}

LL SMax(IT a, IT b)
{
	LL sc = *a, smax = *a;
	for (a++; a <= b; a++)
	{
		if (sc + *a < *a)
			sc = *a;
		else
			sc += *a;
		if (sc > smax)
			smax = sc;
	}
	return smax;
}