rt.

觉得 $600$ ms 就可以了，因为现在的时限线段树可以卡过去。

#include <bits/stdc++.h>

using namespace std;

int read() {
	char ch;
	int f = 1;
    while ((ch = getchar()) < '0') {
    	if (ch == '-') f = -1;
	}
    int x = ch ^ '0';
    while ((ch = getchar()) >= '0') {
        x = (x << 3) + (x << 1) + (ch ^ '0');
    }
    return x * f;
}

const int N = 1e5 + 7;

int n, m, a[N];

struct node {
	int l;
	int r;
	int dat;
}ST[N * 3];

void build(int node_num, int l, int r) {
	ST[node_num].l = l;
	ST[node_num].r = r;
	if (l == r) {
		ST[node_num].dat = a[l];
		return;
	}
	build(node_num << 1, l, l + r >> 1);
	build(node_num << 1 | 1, (l + r >> 1) + 1, r);
	ST[node_num].dat = max(ST[node_num << 1].dat, ST[node_num << 1 | 1].dat);
}

int ask(int node_num, int tar_l, int tar_r) {
	if (ST[node_num].l > tar_r or ST[node_num].r < tar_l) return INT_MIN;
	if (ST[node_num].l >= tar_l && ST[node_num].r <= tar_r) return ST[node_num].dat;
	return max(ask(node_num << 1, tar_l, tar_r), ask(node_num << 1 | 1, tar_l, tar_r));
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	build(1, 1, n);
	while (m--) {
		int l, r;
		l = read(), r = read();
		printf ("%d\n", ask(1, l, r));
	}
	return 0;
}