#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> v3i;
typedef vector<v3i> v4i;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back
struct Random {
mt19937 rnd;
Random(): rnd(random_device{}()) {
rnd.seed(chrono::system_clock::now().time_since_epoch().count());
}
int rand_int(int l, int r) {
return uniform_int_distribution(l, r)(rnd);
}
};
Random rnd;
/*
Persistent Multiset data struct
*/
struct BTreap {
BTreap *lt, *rt;
int sz, v, pr; // size, value, and priority
BTreap(BTreap* a_lt, BTreap* a_rt, int a_v): lt(a_lt), rt(a_rt), sz(1), v(a_v), pr(rnd.rand_int(0, numeric_limits<int>::max())) {
if(lt != nullptr) sz += lt->sz;
if(rt != nullptr) sz += rt->sz;
}
};
inline int btreap_sz(BTreap* tr) {
return (tr == nullptr ? 0 : tr->sz);
}
/*
Merges two treaps together, respecting the BST and treap invariants
*/
BTreap* merge_btreap(BTreap* t1, BTreap* t2) {
if(t1 == nullptr) return t2;
if(t2 == nullptr) return t1;
if(t1 != nullptr && t2 != nullptr) {
if(t1->pr >= t2->pr) swap(t1, t2);
if(t2->v > t1->v) {
// make t2 the right child of t1
return new BTreap(t1->lt, merge_btreap(t1->rt, t2), t1->v);
} else {
// make t2 the left child of t1
return new BTreap(merge_btreap(t1->lt, t2), t1->rt, t1->v);
}
}
}
/*
Splits a treap into two, given the value v
left: <= v
right: > v
*/
pair<BTreap*, BTreap*> split_btreap(BTreap* tr, int v) {
if(tr == nullptr) {
return {nullptr, nullptr};
}
if(v == tr->v) {
return {new BTreap(tr->lt, nullptr, tr->v), tr->rt};
} else if (v > tr->v) {
// split to the right
if(tr->rt == nullptr) {
return {tr, nullptr};
} else {
auto [lsplit, rsplit] = split_btreap(tr->rt, v);
return {new BTreap(tr->lt, lsplit, tr->v), rsplit};
}
} else {
// split to the left
if(tr->lt == nullptr) {
return {nullptr, tr};
} else {
auto [lsplit, rsplit] = split_btreap(tr->lt, v);
return {lsplit, new BTreap(rsplit, tr->rt, tr->v)};
}
}
}
BTreap* insert(BTreap* tr, int v) {
BTreap* nw = new BTreap(nullptr, nullptr, v);
auto [lt, rt] = split_btreap(tr, v);
return merge_btreap(merge_btreap(lt, nw), rt);
}
BTreap* _unify(BTreap* t1, BTreap* t2) {
BTreap* res = t2;
if(t1 == nullptr) return t2;
if(t2 == nullptr) return t1;
res = insert(res, t1->v);
if(t1->lt != nullptr) res = _unify(t1->lt, res);
if(t1->rt != nullptr) res = _unify(t1->rt, res);
return res;
}
BTreap* unify(BTreap* t1, BTreap* t2) {
if(btreap_sz(t1) > btreap_sz(t2)) swap(t1, t2);
return _unify(t1, t2);
}
void _inorder_print_btreap(BTreap* root) {
if(root == nullptr) {
return;
}
cerr << "(";
_inorder_print_btreap(root->lt);
cerr << root->v;
_inorder_print_btreap(root->rt);
cerr << ")";
}
void inorder_print_btreap(BTreap* root) {
_inorder_print_btreap(root);
cerr << endl;
}
BTreap* btreapify(const vi& a) {
BTreap* tr = nullptr;
int n = a.size();
for(int i = 0; i < n; i++) {
tr = insert(tr, a[i]);
}
return tr;
}
int btreap_leq(BTreap* tr, int v) {
if(tr == nullptr) return 0;
if(tr->v <= v) return btreap_sz(tr->lt) + 1 + btreap_leq(tr->rt, v);
else return btreap_leq(tr->lt, v);
}
int btreap_geq(BTreap* tr, int v) {
if(tr == nullptr) return 0;
if(tr->v >= v) return btreap_sz(tr->rt) + 1 + btreap_geq(tr->lt, v);
else return btreap_geq(tr->rt, v);
}
/*
Treap of BSTs
Note: does not need to be persistent
*/
struct Treap {
Treap *lt, *rt;
BTreap *items;
int v, pr;
Treap(int a_v): lt(nullptr), rt(nullptr), items(nullptr), v(a_v), pr(rnd.rand_int(0, numeric_limits<int>::max())) {};
};
Treap* make_treap_node(int v) {
Treap* res = new Treap(v);
res->items = new BTreap(nullptr, nullptr, v);
return res;
}
inline int treap_sz(Treap* tr) {
return (tr == nullptr ? 0 : btreap_sz(tr->items));
}
inline Treap* treap_pull(Treap* tr) {
if(tr == nullptr) return tr;
tr->items = unify((tr->lt == nullptr ? nullptr : tr->lt->items), (tr->rt == nullptr ? nullptr : tr->rt->items));
tr->items = insert(tr->items, tr->v);
return tr;
}
inline Treap* treap_merge(Treap* t1, Treap* t2) {
if(t1 == nullptr) return t2;
if(t2 == nullptr) return t1;
if(t1->pr < t2->pr) {
// make t2 the right child of t1
t1->rt = treap_merge(t1->rt, t2);
treap_pull(t1);
return t1;
} else {
// make t1 the left child of t2
t2->lt = treap_merge(t1, t2->lt);
treap_pull(t2);
return t2;
}
}
inline int leftmost_treap_item(Treap* tr) {
if(tr == nullptr) return -1;
if(tr->lt == nullptr) return tr->v;
return leftmost_treap_item(tr->lt);
}
/*
returns two treaps, where the left treap has size sz
*/
inline pair<Treap*, Treap*> treap_split(Treap* tr, int sz) {
if(tr == nullptr) return {nullptr, nullptr};
int lsz = treap_sz(tr->lt);
if(lsz + 1 == sz) {
Treap* tmp = tr->rt;
tr->rt = nullptr;
treap_pull(tr);
return {tr, tmp};
} else if(lsz < sz) {
// split point is to the right
auto [l, r] = treap_split(tr->rt, sz - lsz - 1);
tr->rt = l;
treap_pull(tr);
return {tr, r};
} else {
// split point is to the left
auto [l, r] = treap_split(tr->lt, sz);
tr->lt = r;
treap_pull(tr);
return {l, tr};
}
}
/*
finds the item at an index i (1-based)
*/
inline int find_item(Treap* tr, int i) {
if(treap_sz(tr->lt) == i - 1) return tr->v;
if(treap_sz(tr->lt) >= i) return find_item(tr->lt, i);
return find_item(tr->rt, i - treap_sz(tr->lt) - 1);
}
/*
finds the first item greater than v
*/
int _strict_upper_bound(Treap* tr, int v) {
if(tr->lt == nullptr) return (tr->v > v ? 1 : 1 + _strict_upper_bound(tr->rt, v));
if(btreap_geq(tr->lt->items, v + 1) > 0) return _strict_upper_bound(tr->lt, v);
else if(tr->v > v) return btreap_sz(tr->lt->items) + 1;
else return btreap_sz(tr->lt->items) + 1 + _strict_upper_bound(tr->rt, v);
}
int strict_upper_bound(Treap* tr, int v) {
if(tr == nullptr) return 0;
if(btreap_geq(tr->items, v + 1) == 0) return 0;
return _strict_upper_bound(tr, v);
}
Treap* treapify(const vi& a) {
// int n = a.size();
Treap* res = nullptr;
for(int v : a) {
Treap* nw_node = make_treap_node(v);
res = treap_merge(res, nw_node);
}
return res;
}
struct query {
int qt, qi, i;
};
typedef vector<query> vq;
pair<bool, Treap*> shuffle_tr(Treap* tr) {
int n = treap_sz(tr);
auto [l, r] = treap_split(tr, n >> 1);
bool done_shuffling = btreap_geq(l->items, leftmost_treap_item(r)) == 0;
if(done_shuffling) return {done_shuffling, treap_merge(l, r)};
Treap* res = nullptr;
while(l != nullptr && r != nullptr) {
int lv = leftmost_treap_item(l), rv = leftmost_treap_item(r);
if(lv < rv) {
// slice off from the left
int lsp_sz = strict_upper_bound(l, rv) - 1;
if(lsp_sz == -1) {
// we're essentially done!
res = treap_merge(res, l);
l = nullptr;
break;
} else {
auto [tmpl, tmpr] = treap_split(l, lsp_sz);
res = treap_merge(res, tmpl);
l = tmpr;
}
} else {
// slice off from the right
int rsp_sz = strict_upper_bound(r, lv) - 1;
if(rsp_sz == -1) {
// we're essentially done!
res = treap_merge(res, r);
r = nullptr;
break;
} else {
auto [tmpl, tmpr] = treap_split(r, rsp_sz);
res = treap_merge(res, tmpl);
r = tmpr;
}
}
}
if(l != nullptr) {
res = treap_merge(res, l);
}
if(r != nullptr) {
res = treap_merge(res, r);
}
return {false, res};
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, q;
cin >> n >> q;
vi a(n, 0);
for(int& v : a) cin >> v;
Treap* tr = treapify(a);
vq qs(q, {0, 0, 0});
vi res(q, 0);
for(int i = 0; i < q; i++) {
cin >> qs[i].qt >> qs[i].qi;
qs[i].i = i;
}
sort(qs.begin(), qs.end(), [](query q1, query q2) {return q1.qt < q2.qt;});
int cur_qi = 0;
int cur_t = 0;
while(true) {
while(cur_qi < q && qs[cur_qi].qt == cur_t) {
res[qs[cur_qi].i] = find_item(tr, qs[cur_qi].qi);
cur_qi++;
}
if(cur_qi == q) break;
auto [is_done, new_tr] = shuffle_tr(tr);
if(is_done) break;
tr = new_tr;
cur_t++;
}
while(cur_qi < q) {
res[qs[cur_qi].i] = find_item(tr, qs[cur_qi].qi);
cur_qi++;
}
for(int i = 0; i < q; i++) {
cout << res[i] << "\n";
}
cout << flush;
return 0;
}
/*
1, 3, 6, 10, 15, 2, 5, 9, 14, 17
*/
