#include <iostream> #include <vector> using namespace std; const int N = 1<<20; int ft[N], a[N], b[N], Ans[N]; vector<int> vec[N]; vector<pair<int, int>> Qr[N]; void Add(int i, int 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){ int l = 0, r = N; while (l + 1 < r){ int mid = (l + r) >> 1; if (get(mid) < k) l = mid; else r = mid; } return l; while (1){ if (ft[i + (i&-i)] < k) i += i&-i; else if (ft[i] >= k) return i-1; else k -= ft[i++]; } return 0; } 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, ind = 0, m = 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++]; m = max(m, b[ind]); vec[m].push_back(b[ind]); Add(m, 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] = vec[k][rem - 1]; } int k = get2(n / 2) + 1, rem = get(k) - n / 2; if (rem){ m = 0; Add(k, -rem); for (int j=vec[k].size() - rem;j < vec[k].size();j++) m = max(m, vec[k][j]), vec[m].push_back(vec[k][j]), Add(m, 1); while (rem--) vec[k].pop_back(); } } for (int i=1;i<=q;i++) cout<<Ans[i]<<'\n'; }