线段树艹过去了，而且打的还不卡常，只加了一个快读 （和远古魔法）。

正常 ST表 都能 $\le450\operatorname{ms}$ 过，所以觉得可以缩到 $0.5\operatorname{s}$。

测评记录 click here，没开 O2（开了更慢？！），最大点 $778\operatorname{ms}$。

#include <iostream>
using namespace std;

#define MS 100005

#define getchar getchar_unlocked

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

struct SegmentTree {
	
	struct node {
		
		int l, r, v;
		
#define ls(idx) ((idx) << 1)
#define rs(idx) (ls(idx) | 1)
		
	} t[MS << 2];
	
	void build(int l, int r, int idx) {
		t[idx].l = l, t[idx].r = r;
		if (l == r) {
			t[idx].v = read();
			return;
		}
		int m = (l + r) >> 1;
		build(l, m, ls(idx));
		build(m + 1, r, rs(idx));
		t[idx].v = max(t[ls(idx)].v, t[rs(idx)].v);
	}
	
	int queryMAX(int l, int r, int idx) {
		if (r < t[idx].l || t[idx].r < l)
			return -0x3f3f3f3f;
		if (l <= t[idx].l && t[idx].r <= r)
			return t[idx].v;
		return max(queryMAX(l, r, ls(idx)), queryMAX(l, r, rs(idx)));
	}
	
} tree;

int n, q;

int main() {
	n = read(); q = read();
	tree.build(1, n, 1);
	while (q --) {
		int l, r;
		l = read(); r = read();
		printf("%d\n", tree.queryMAX(l, r, 1));
	}
	return 0;
}