回滚莫队，复杂度 $\mathcal O(n\sqrt{m})$（而且块长没取到最优），无快读快写和任何卡常，最大点 686ms。

只是想找一道最最最简单的回滚莫队例题，本来想拿 70，结果直接过了。

// Problem: P3865 【模板】ST 表
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3865
// Memory Limit: 125 MB
// Time Limit: 800 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 2e6+5;

int n, m, k, a[N], L[N], R[N], pos[N], sz, tot, ans[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct Query {
	int l, r, id;
	Query(int a=0, int b=0, int c=0) : l(a), r(b), id(c) {}
	friend bool operator < (const Query& a, const Query& b) {
		if(pos[a.l] != pos[b.l]) return a.l < b.l;
		return a.r < b.r;
	}
}q[N];
void initBlock() {
	sz = sqrt(n);
	while(++tot) {
		L[tot] = R[tot-1] + 1;
		R[tot] = min(sz * tot, n);
		rep(i, L[tot], R[tot]) pos[i] = tot;
		if(R[tot] == n) break;
	}
}

int main() {
	scanf("%d%d", &n, &m);
	rep(i, 1, n) scanf("%d", &a[i]);
	initBlock();
	rep(i, 1, m) {
		int l, r;
		scanf("%d%d", &l, &r);
		if(pos[l] != pos[r]) q[++k] = Query(l, r, i);
		else ans[i] = *max_element(a+l, a+1+r);
	}
	sort(q+1, q+1+k);
	int l = 0, r = 0, save = 0, now = 0;
	rep(i, 1, k) {
		if(i == 1 || pos[q[i].l] != pos[q[i-1].l]) {
			r = R[pos[q[i].l]];
			save = now = 0;
		}
		while(r < q[i].r) save = now = max(now, a[++r]);
		l = R[pos[q[i].l]] + 1;
		while(l > q[i].l) now = max(now, a[--l]);
		ans[q[i].id] = now;
		now = save;
	}
	rep(i, 1, m) printf("%d\n", ans[i]);
	return 0;
}