观察到一轮操作会先选两个数中较小的，再把后面的更小的数选上。

将这样的区间的第一个数排序（把它看做代表元）。

每个区间的第一个数单调递增。就是一个单调数组。

现在考虑一次洗牌会有什么影响。

若 $\frac{n}{2}$ 和 $\frac{n}{2} + 1$ 不在一段内，没有影响。

若在一个块内，后面一段会被分成很多个小段。

注意到一个块内的数的顺序与原序列相同，于是我们可以预处理下一个比 $a_i$ 大的数 $nxt_{i}$。

将每个区间开头插入权值线段树，维护每个区间长度。

每次在线段树上二分，找到包含 $\frac{n}{2}$ 的区间。设这个区间为 $[l, r]$，把它分成两段 $[l, \frac{n}{2}]$ 和 $[\frac{n}{2} + 1, r]$ 对后面的区间暴力分成许多小块，由于最多分解 $n$ 次。

所以时间复杂度 $(n + m) \log_n$。

代码：

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define sc second
const int N = 2e5 + 10, M = 1e6 + 10;
int n, T;
int a[N], pos[N], nxt[N], ans[M];
int sum[N << 2];
vector<pair<int, int> > q[N];
void change(int p, int l, int r, int x, int y) {
    if (l > x || r < x)
        return;
    if (l == r) {
        sum[p] = y;
        return;
    }
    int mid = (l + r) / 2;
    change(p * 2, l, mid, x, y), change(p * 2 + 1, mid + 1, r, x, y);
    sum[p] = sum[p * 2] + sum[p * 2 + 1];
}

int query(int p, int l, int r, int x) {
    if (l == r)
        return sum[p];
    int mid = (l + r) / 2;
    if (x <= mid)
        return query(p * 2, l, mid, x);
    return query(p * 2 + 1, mid + 1, r, x);
}

pair<int, int> queryk(int p, int l, int r, int k) {
    if (l == r) {
        return { l, k };
    }
    int mid = (l + r) / 2;
    if (sum[p * 2] < k) {
        return queryk(p * 2 + 1, mid + 1, r, k - sum[p * 2]);
    }
    return queryk(p * 2, l, mid, k);
}

int main() {
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(0);
    freopen("tors.in", "r", stdin);
    freopen("tors.out", "w", stdout);
    cin >> n >> T;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    vector<int> stk;
    for (int i = n; i >= 1; i--) {
        while (!stk.empty() && a[*stk.rbegin()] < a[i]) {
            stk.pop_back();
        }
        if (!stk.empty())
            nxt[i] = *stk.rbegin();
        else
            nxt[i] = n + 1;
        stk.push_back(i);
    }
    for (int i = 1; i <= n; i = nxt[i]) {
        change(1, 1, n, a[i], nxt[i] - i);
    }
    for (int i = 1; i <= T; i++) {
        int t, p;
        cin >> t >> p;
        q[min(t, n)].push_back({ p, i });
    }
    for (int i = 0; i <= n; i++) {
        for (auto t : q[i]) {
            auto res = queryk(1, 1, n, t.fi);
            ans[t.sc] = a[pos[res.first] + res.second - 1];
        }
        int mid = n / 2 + 1;
        auto t = queryk(1, 1, n, mid);
        int len = query(1, 1, n, t.first);
        if (t.second == 1)
            continue;
        change(1, 1, n, t.first, t.second - 1);
        for (int j = pos[t.first] + t.second - 1; j <= pos[t.first] + len - 1; j = nxt[j]) {
            change(1, 1, n, a[j], min(pos[t.first] + len, nxt[j]) - j);
        }
    }
    for (int i = 1; i <= T; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}