#include <iostream>
#include <cstdio>

inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < 48 || ch > 57) if (ch == '-') f = -1, ch = getchar();
	while (ch > 47 && ch < 58) x = x * 10 + (ch & 15), ch = getchar();
	return x * f;
}

struct log2map {
	int *log;
	inline log2map (const unsigned n)
	{
		log = new int[n]; log[0] = -1;
		for (unsigned i = 1; i < n; ++i) log[i] = log[i >> 1] + 1;
	}
	int operator()(int n) { return log[n]; }
};
log2map Log2(100005);

struct STable 
{
//	int *dp[20];
//	STable (const int& n = 2)
//	{
//		const int l = (int)log2(n << 1);
////		dp = new int[n][l];
//		int i = 0; dp[0] = new int[100005];
//		while (i < l) dp[i] = dp[i - 1] + n;
//	}
	int dp[10005][20] = {};
	inline void init(std::istream& in, unsigned n)
	{
		unsigned int l = Log2(n);
		for (unsigned i = 0; i < n; ++i) in >> dp[i][0];
		for (unsigned j = 1; j <= l; ++j)
			for (unsigned i = 0; i + (1<<j) <= n; ++i)
				dp[i][j] = std::max(dp[i][j - 1], dp[i + (1<<j-1)][j - 1]);
	}
	inline void init(int in(), unsigned n)
	{
		unsigned int l = Log2(n);
		for (unsigned i = 0; i < n; ++i) dp[i][0] = in();
		for (unsigned j = 1; j <= l; ++j)
			for (unsigned i = 0; i + (1<<j) <= n; ++i)
				dp[i][j] = std::max(dp[i][j - 1], dp[i + (1<<j-1)][j - 1]);
	}
	inline int query_max(unsigned l, unsigned r)
	{
		unsigned int log = Log2(r - l + 1);
		return std::max(dp[l][log], dp[r - (1<<log) + 1][log]);
	}
};

int main()
{
	std::ios::sync_with_stdio(false);
	STable a;
	int n, m, l, r;
	std::cin >> n >> m;
	a.init(read, n); // 使用快读
//	a.init(std::cin, n); // 使用 cin
	while (m--)
	{
		std::cin >> l >> r;
		std::cout << a.query_max(l - 1, r - 1) << '\n';
	}
	return 0;
}

使用快读（read) 0 pts
使用std::cin 70 pts