#include <iostream> #include <vector> using namespace std; const int N = 1<<18; int ft[N], a[N], Ans[N<<2], b[N], sz[N], st[N], Nxt[N]; vector<pair<int, int>> Qr[N]; vector<int> stk; void Add(int i, int v){ sz[i] += v; for (; i < N; i += i&-i) ft[i] += v; } int get(int i, int ans = 0){ for (; i; i -= i&-i) ans += ft[i]; return ans; } int get2(int k, int i = 1){ while (1){ if (ft[i + (i&-i)] < k) i += i&-i; else if (ft[i] >= k) return i-1; else k -= ft[i++]; } return -1; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q; cin>>n>>q; for (int i=1;i<=n;i++) cin>>a[i]; for (int i=1, t, id;i<=q;i++){ cin>>t>>id; t = min(t, n); if (t == 0) Ans[i] = a[id]; else Qr[t].push_back({id, i}); } int l1 = 1, l2 = n / 2 + 1, m = 0, ind = 0; while (ind < n){ if (l1 <= n / 2 and (l2 == n + 1 or a[l2] > a[l1])) b[++ind] = a[l1++]; else b[++ind] = a[l2++]; st[b[ind]] = ind; m = max(m, b[ind]); Add(m, 1); } for (int i=1;i<=n;i++){ while (stk.size() > 0 and b[stk.back()] < b[i]) Nxt[stk.back()] = i, stk.pop_back(); stk.push_back(i), Nxt[i] = n + 1; } for (int i=1;i<=n;i++){ for (auto [id, id2] : Qr[i]){ int k = get2(id) + 1, rem = id - get(k - 1); Ans[id2] = b[st[k] + rem - 1]; } int k = get2(n / 2) + 1, rem = get(k) - n / 2; for (int j=st[k] + sz[k] - rem;j < st[k] + sz[k];j = Nxt[j]) Add(b[j], min(sz[k] + st[k], Nxt[j]) - j); Add(k, -rem); } for (int i=1;i<=q;i++) cout<<Ans[i]<<'\n'; }