rt，蒟蒻刚学 ST qwq

#include <bits/stdc++.h>
using namespace std;
const int _ = 1e5;
int a[_];
int n;

struct ST_min {
	int f[(int)1e4][22];
	void init() {
		int k = log2(n);
		for (int i = 1; i <= n; i ++) f[i][0] = a[i];
		for (int j = 1; 1<<j <= n; j ++)
			for (int i = 1; i + (1 << j) - 1 <= n; i ++)
				f[i][j] = min(f[i][j - 1], f[i + (1 << j)][j - 1]);
	}
	int rmq(int l, int r) {
		int k = log2(r - l + 1);
		return min(f[l][k], f[r - (1 << k) + 1][k]);
	}
};
struct ST_max {
	int g[(int)1e4][22];
	void init() {
		int k = log2(n);
		for (int i = 1; i <= n; i ++) g[i][0] = a[i];
		for (int j = 1; 1<<j <= n; j ++)
			for (int i = 1; i + (1 << j) - 1 <= n; i ++)
				g[i][j] = max(g[i][j - 1], g[i + (1 << j)][j - 1]);
	}
	int rmq(int l, int r) {
		int k = log2(r - l + 1);
		return max(g[l][k], g[r - (1 << k) + 1][k]);
	}
};
signed main() {

	int T;
	cin >> n >> T;
	for(int i = 1; i <= n; i ++)
		cin >> a[i];

	ST_max tree1;
	tree1.init();

	while(T--) {
		int l, r;
		cin >> l >> r;
		cout << tree1.rmq(l, r) << endl;
	}

	return 0;
}