#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;
/*
Range max treap
*/
struct Treap {
Treap* lt, *rt;
int sz, mx, v, pr;
Treap(int a_v): lt(nullptr), rt(nullptr), sz(1), mx(a_v), v(a_v), pr(rnd.rand_int(0, numeric_limits<int>::max())) {};
};
inline int treap_sz(Treap* tr) {
return (tr == nullptr ? 0 : tr->sz);
}
inline Treap* treap_pull(Treap* tr) {
if(tr == nullptr) return tr;
tr->sz = treap_sz(tr->lt) + treap_sz(tr->rt) + 1;
tr->mx = tr->v;
if(tr->lt != nullptr) tr->mx = max(tr->mx, tr->lt->mx);
if(tr->rt != nullptr) tr->mx = max(tr->mx, tr->rt->mx);
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 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) {
auto [l, r] = treap_split(tr->lt, sz);
tr->lt = r;
treap_pull(tr);
return {l, tr};
} else {
auto [l, r] = treap_split(tr->rt, sz - lsz - 1);
tr->rt = l;
treap_pull(tr);
return {tr, r};
}
}
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);
}
inline 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(tr->lt->mx > v) return _strict_upper_bound(tr->lt, v);
else if(tr->v > v) return treap_sz(tr->lt) + 1;
else return treap_sz(tr->lt) + 1 + _strict_upper_bound(tr->rt, v);
}
inline int strict_upper_bound(Treap* tr, int v) {
if(tr == nullptr) return 0;
if(tr->mx <= v) return 0;
return _strict_upper_bound(tr, v);
}
inline int find_item(Treap* tr, int i) {
assert(tr != nullptr);
int lsz = treap_sz(tr->lt);
if(lsz == i - 1) return tr->v;
if(lsz >= i) return find_item(tr->lt, i);
return find_item(tr->rt, i - lsz - 1);
}
Treap* treapify(const vi& a) {
Treap* res = nullptr;
for(int v : a) {
res = treap_merge(res, new Treap(v));
}
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 = l->mx < leftmost_treap_item(r);
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};
}
void _inorder_traverse(Treap* tr) {
if(tr == nullptr) return;
_inorder_traverse(tr->lt);
cerr << tr->v << " ";
_inorder_traverse(tr->rt);
}
void inorder_traverse(Treap* tr) {
_inorder_traverse(tr);
cerr << endl;
}
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);
// inorder_traverse(tr);
// for(int i = 0 ; i < n; i++) {
// cerr << find_item(tr, i + 1) << " ";
// }
// cerr << endl;
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
*/
