操作没有什么性质，唯一一个性质是，操作次数不超过 \(\log n\)（每次至多保留一半元素）。于是我们可以直接模拟操作。
但是肯定不能直接模拟。考虑先对原序列模拟一次，求出经过 \(i\) 次操作后保留的位置集合 \(S_i\)。那么只保留 \([l, r]\) 的元素，可能会造成端点处的元素由不是局部最值变成是局部最值。同时因为新添了这些元素，和它们相邻的元素可能会由是局部最值变成不是局部最值。
考虑如下的递归过程。维护当前进行了 \(i\) 次操作，位置集合是 \(L \cup S_{i, l \sim r} \cup R\)（要维护 \(L, R\)）。如果 \(r - l + 1 \le 1\)，就可以直接模拟；否则考虑 \(S_{i, l}\) 和 \(S_{i, r}\) 的变化，可以先把 \(S_{i, l}\) 加入 \(L\)，把 \(S_{i, r}\) 加入 \(R\)，假设把 \(S_{i, l + 1}\) 加入 \(L\)，把 \(S_{i, r - 1}\) 加入 \(R\)，然后模拟一次。计算下一层的 \(l, r\)，分别 upper_bound 和 lower_bound 一次即可。
时间复杂度 \(O(n + q \log^2 n)\)。
code
// Problem: F. Local Deletions
// Contest: Codeforces - Codeforces Round 911 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1900/F
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
typedef vector<int> vi;
const int maxn = 100100;
int n, m, a[maxn];
vi b[20];
inline vi work(vi vc, int op) {
if ((int)vc.size() <= 1) {
return vc;
}
int n = (int)vc.size();
vi res;
if (op) {
if (a[vc[0]] < a[vc[1]]) {
res.pb(vc[0]);
}
for (int i = 1; i + 1 < n; ++i) {
if (a[vc[i - 1]] > a[vc[i]] && a[vc[i]] < a[vc[i + 1]]) {
res.pb(vc[i]);
}
}
if (a[vc[n - 2]] > a[vc[n - 1]]) {
res.pb(vc[n - 1]);
}
} else {
if (a[vc[0]] > a[vc[1]]) {
res.pb(vc[0]);
}
for (int i = 1; i + 1 < n; ++i) {
if (a[vc[i - 1]] < a[vc[i]] && a[vc[i]] > a[vc[i + 1]]) {
res.pb(vc[i]);
}
}
if (a[vc[n - 2]] < a[vc[n - 1]]) {
res.pb(vc[n - 1]);
}
}
return res;
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
b[0].pb(i);
}
for (int i = 1; i < 20; ++i) {
b[i] = work(b[i - 1], i & 1);
}
while (m--) {
int l, r;
scanf("%d%d", &l, &r);
--l;
--r;
vector<int> L, R;
for (int i = 0;; ++i) {
if (l >= r) {
for (int j = l; j <= r; ++j) {
L.pb(b[i][j]);
}
for (int j : R) {
L.pb(j);
}
while ((int)L.size() > 1) {
L = work(L, (i & 1) ^ 1);
++i;
}
printf("%d\n", a[L[0]]);
break;
}
L.pb(b[i][l]);
L.pb(b[i][l + 1]);
L = work(L, (i & 1) ^ 1);
if (L.back() == b[i][l + 1]) {
L.pop_back();
}
R.insert(R.begin(), b[i][r]);
R.insert(R.begin(), b[i][r - 1]);
R = work(R, (i & 1) ^ 1);
if (R[0] == b[i][r - 1]) {
R.erase(R.begin());
}
l = upper_bound(b[i + 1].begin(), b[i + 1].end(), b[i][l]) - b[i + 1].begin();
r = lower_bound(b[i + 1].begin(), b[i + 1].end(), b[i][r]) - b[i + 1].begin() - 1;
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}