#include <bits/stdc++.h>
#include <random>
using namespace std;
#define lf "\n"
#define ff endl
#define _ << ' ' <<
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
#define infos(str) do { fprintf(stderr, str"\n"); } while(0)
#define infor(str, ...) do { fprintf(stderr, str, __VA_ARGS__); } while(0)
#define infof(str, ...) do { fprintf(stderr, str"\n", __VA_ARGS__); } while(0)
#ifndef DEBUG
#undef infos
#undef infor
#undef infof
#define infos(str)
#define infor(str, ...)
#define infof(str, ...)
#endif
using ll = long long;
constexpr int LOG = 20;
constexpr int MOD = 1e9+7;
constexpr int MAXN = 1e5+7;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
using Treap = struct Node *;
struct Node {
int pri;
int val;
int sz;
int id;
Treap l;
Treap r;
Node(int val): pri(mt()), val(val), sz(1) {
static int id = 0;
infof("- Created new node %d with %d", id, val);
this->id = id++;
l = r = NULL;
}
void operator~(void) {
delete l;
delete r;
}
};
int sz(Treap v) {
return v ? v->sz : 0;
}
void pull(Treap v) {
if(!v) return;
v->sz = sz(v->l) + 1 + sz(v->r);
}
int first(Treap v) {
if(v->l) return first(v->l);
return v->val;
}
Treap merge(Treap l, Treap r) {
if(!l || !r) return l ? l : r;
//infof("... Merging %d with %d", l->id, r->id);
if(l->pri > r->pri) {
l->r = merge(l->r, r);
pull(l);
if(l->r) assert(l->r->id != l->id);
return l;
}
r->l = merge(l, r->l);
pull(r);
if(r->l) assert(r->l->id != r->id);
return r;
}
array<Treap, 2> split(Treap v, int i) {
if(!v) return {NULL, NULL};
//infof("... Splitting %d | sz_l: %d, sz_r: %d", v->id, sz(v->l), sz(v->r));
if(sz(v->l) >= i) {
if(v->l) assert(v->l->id != v->id);
auto [l, r] = split(v->l, i);
v->l = r;
pull(v);
return {l, v};
} else {
if(v->r) assert(v->r->id != v->id);
auto [l, r] = split(v->r, i - sz(v->l) - 1);
v->r = l;
pull(v);
return {v, r};
}
}
Treap find(Treap v, int i) {
if(!v) return 0;
//infof("... Finding %d [%d, %d]", i, sz(v->l), sz(v->r));
if(sz(v->l) == i)
return v;
if(sz(v->l) > i && v->l)
assert(v->l->id != v->id);
if(sz(v->r) > i && v->r)
assert(v->r->id != v->id);
if(sz(v->l) > i)
return find(v->l, i);
else return find(v->r, i - sz(v->l) - 1);
}
void print(Treap v) {
if(!v) return;
print(v->l);
infor("%d [%d] ", v->val, v->id);
print(v->r);
}
Treap shuffler(Treap v, int k) {
pull(v);
const int N = sz(v);
auto [l, r] = split(v, N / 2);
infof("K = %d: split into sizes: sz_l %d, sz_r %d", k, sz(l), sz(r));
assert(sz(l) == sz(r));
v = NULL;
Treap block_l = NULL, block_r = NULL;
for(; sz(l) && sz(r);) {
if(!block_l) {
infor("- Splitting L | sz is %d | ", sz(l));
auto ret = split(l, k);
block_l = ret[0], l = ret[1];
infof("block: %d ; rest: %d", sz(block_l), sz(l));
}
if(!block_r) {
infor("- Splitting R | sz is %d | ", sz(r));
auto ret = split(r, k);
block_r = ret[0], r = ret[1];
infof("block: %d ; rest: %d", sz(block_r), sz(r));
}
infof("- First L: %d | First R: %d", first(block_l), first(block_r));
if(first(block_l) < first(block_r))
v = merge(v, block_l), block_l = NULL;
else v = merge(v, block_r), block_r = NULL;
}
l = merge(block_l, l);
r = merge(block_r, r);
if(sz(l)) v = merge(v, l);
if(sz(r)) v = merge(v, r);
return v;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int N, Q; cin >> N >> Q;
vector<int> V(N);
for(auto &x: V) cin >> x;
vector<array<int, 2>> Qs(Q);
for(auto &[t, i]: Qs) cin >> t >> i, i--;
vector<int> order(Q); iota(all(order), 0);
sort(all(order), [&](int i, int j) -> bool {
return Qs[i] < Qs[j];
});
vector<int> ans(Q);
vector<Treap> nodes(N);
Treap v = new Node(V[0]);
nodes[0] = v;
for(int i = 1; i < N; ++i)
v = merge(v, nodes[i] = new Node(V[i]));
infof("Initialized treap with %d nodes", sz(v));
infos("Treap at start:");
print(v); infos("");
int it = 0;
int curr = 0;
for(int q: order) {
infos("================");
infof("%d: size of treap is %d", it++, sz(v));
auto [t, idx] = Qs[q];
infof("Solving %d %d", t, idx);
infos("");
for(; curr < min(t, N); ++curr) {
v = shuffler(v, 1);
infos("");
infof("Treap at %d:", curr + 1);
print(v); infos("");
infos("");
}
infof("searching index %d in treap of size %d", idx, sz(v));
Treap node = find(v, idx);
assert(node);
ans[q] = node->val;
infof("ANSWER FOR %d: %d", q, ans[q]);
}
for(auto x: ans)
cout << x << lf;
cout.flush();
infof("treap has %d nodes", sz(v));
print(v); infos("");
for(auto x: nodes) delete x;
}
