#include <fstream>

using namespace std;

const int lInt = 100000 * 4 + 500;
const int oo = -19000000;
class SequenceQuery
{
	int n, m;

	int ArbInt[lInt];

	void UpdateTree(int node, pair < int, int > extr, int idx, int x)
	{
		if(extr.first == extr.second)	{

			ArbInt[node] = x;
			return;
		}

		int mid = (extr.first + extr.second) >> 1;

		if(x <= mid)	
			UpdateTree(2 * node, make_pair(extr.first, mid), idx, x);
		else	
			UpdateTree(2 * node + 1, make_pair(mid + 1, extr.second), idx, x);

		ArbInt[node] = max(ArbInt[2 * node], ArbInt[2 * node + 1]);
		ArbInt[node] = max(ArbInt[node], ArbInt[2 * node] + ArbInt[2 * node + 1]);
	}

	void Querry(int node, pair < int, int > extr, pair < int, int > curInt, int *solution)
	{
		if(curInt.first <= extr.first && extr.second <= curInt.second)	{

			*solution = max(*solution, ArbInt[node]);
			return;
		}

		int mid = (extr.first + extr.second) >> 1;

		if(curInt.first <= mid)
			Querry(2 * node, make_pair(extr.first, mid), curInt, solution);
		if(mid < curInt.second)
			Querry(2 * node + 1, make_pair(mid + 1, extr.second), curInt, solution);
	}

public :
	void Compute()
	{
		ifstream inputFile("sequencequery.in");
		ofstream outputFile("sequencequery.out");

		inputFile >> n >> m;

		for(int x, i = 1; i <= n; ++i)	
		{
			inputFile >> x;
			UpdateTree(1, make_pair(1, n), i, x);
		}

		int solution;

		for(int x, y, i = 1; i <= m; ++i)	
		{
			inputFile >> x >> y;

			solution = oo;
			Querry(1, make_pair(1, n), make_pair(x, y), &solution);

			outputFile << solution << '\n';
		}

		outputFile.close();
		inputFile.close();
	}
};

int main()
{
	SequenceQuery obj;

	obj.Compute();

	return 0;
}