#include <bits/stdc++.h>
using namespace std;
int n, q, arr[202020];
int ans[1010101];
int res[202020];
int nxt[202020];
stack< pair<int, int> > S;
int qnum = 1;
struct query {
int time, idx, ord;
bool operator<(const query &other) const {
if (time == other.time) return idx < other.idx;
return time < other.time;
}
} queries[1010101];
struct segment {
int first, st, ed, sz;
bool operator<(const segment &other) const {
return first > other.first;
}
};
set<segment> segs;
struct segtree {
int tree[808080];
void update(int v, int st, int ed, int idx, int val) {
if (st > idx) return;
if (ed < idx) return;
if (st == ed) {
tree[v] = val;
return;
}
int mid = (st + ed) / 2;
update(2 * v, st, mid, idx, val);
update(2 * v + 1, mid + 1, ed, idx, val);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
pair<int, int> get(int v, int st, int ed, int val) {
if (st == ed) return {st, val - tree[v]};
int mid = (st + ed) / 2;
if (tree[2 * v] < val) return get(2 * v + 1, mid + 1, ed, val - tree[2 * v]);
else return get(2 * v, st, mid, val);
}
} sumtree;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = 1; i <= q; i++) {
cin >> queries[i].time >> queries[i].idx;
queries[i].ord = i;
queries[i].time = min(queries[i].time, n);
}
sort(queries + 1, queries + q + 1);
while (qnum <= q) {
if (queries[qnum].time > 0) break;
ans[queries[qnum].ord] = arr[queries[qnum].idx];
qnum++;
}
for (int i = 1; i <= n; i++) {
while (!S.empty()) {
if (S.top().second < arr[i]) {
nxt[S.top().first] = i;
S.pop();
}
else break;
}
S.push({i, arr[i]});
}
while (!S.empty()) {
nxt[S.top().first] = n + 1;
S.pop();
}
int k = 1;
while (nxt[k] <= n/2) {
segs.insert({arr[k], k, nxt[k] - 1, nxt[k] - k});
sumtree.update(1, 1, n, arr[k], nxt[k] - k);
k = nxt[k];
}
segs.insert({arr[k], k, n/2, n/2 - k + 1});
sumtree.update(1, 1, n, arr[k], n/2 - k + 1);
k = n/2 + 1;
while (nxt[k] <= n) {
segs.insert({arr[k], k, nxt[k] - 1, nxt[k] - k});
sumtree.update(1, 1, n, arr[k], nxt[k] - k);
k = nxt[k];
}
segs.insert({arr[k], k, n, n - k + 1});
sumtree.update(1, 1, n, arr[k], n - k + 1);
int cnt = 0, p = n;
for (int t = 1; t <= queries[q].time; t++) {
while (qnum <= q) {
if (queries[qnum].time > t) break;
if (res[queries[qnum].idx] > 0) ans[queries[qnum].ord] = res[queries[qnum].idx];
else {
pair<int, int> val = sumtree.get(1, 1, n, queries[qnum].idx);
assert(segs.find({val.first, 0, 0, 0}) != segs.end());
ans[queries[qnum].ord] = arr[segs.find({val.first, 0, 0, 0})->ed + val.second];
}
qnum++;
}
while (1) {
if (cnt + segs.begin()->sz > n/2) break;
cnt += segs.begin()->sz;
for (int i = segs.begin()->ed; i >= segs.begin()->st; i--) {
res[p--] = arr[i];
}
sumtree.update(1, 1, n, segs.begin()->first, 0);
segs.erase(segs.begin());
}
if (cnt == n/2) continue;
segment div = *segs.begin();
segs.erase(segs.begin());
segs.insert({div.first, div.st, div.st + cnt + div.sz - n/2 - 1, cnt + div.sz - n/2});
sumtree.update(1, 1, n, div.first, cnt + div.sz - n/2);
k = div.st + cnt + div.sz - n/2;
while (nxt[k] <= div.ed) {
segs.insert({arr[k], k, nxt[k] - 1, nxt[k] - k});
sumtree.update(1, 1, n, arr[k], nxt[k] - k);
k = nxt[k];
}
segs.insert({arr[k], k, div.ed, div.ed - k + 1});
sumtree.update(1, 1, n, arr[k], div.ed - k + 1);
}
for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
return 0;
}
