#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<int> tree;
int cnt = 0;
auto update = [&](int pos, int amt) -> void {
for (; pos <= cnt; pos += pos & (-pos)) tree[pos] += amt;
};
auto sum = [&](int pos) -> int {
int res = 0;
for (; pos >= 1; pos -= pos & (-pos)) res += tree[pos];
return res;
};
auto query = [&](int amt) -> int {
int pos = 0, curSum = 0;
for (int i = 20; i >= 0; --i) {
if (pos + (1 << i) <= cnt && curSum + tree[pos + (1 << i)] < amt) {
curSum += tree[pos + (1 << i)];
pos += (1 << i);
}
}
return pos + 1;
};
int n, q;
cin >> n >> q;
vector<int> initial(n + 1);
for (int i = 1; i <= n; ++i) cin >> initial[i];
vector<int> nxtLargest(n + 1), stk = {1'000'000'000};
for (int i = n; i >= 1; --i) {
while (stk.back() != 1e9 && initial[stk.back()] < initial[i])
stk.pop_back();
nxtLargest[i] = stk.back();
stk.push_back(i);
}
set<pair<int, pair<int, int>>> s, allBlocks;
vector<pair<int, pair<int, int>>> invComp(1);
map<pair<int, pair<int, int>>, int> comp;
auto intoBlocks = [&](int l, int r, bool first = false) -> void {
for (int i = l; i <= r; ++i) {
int nxt = min(nxtLargest[i] - 1, r);
s.insert({initial[i], {i, nxt}});
if (first)
allBlocks.insert({initial[i], {i, nxt}});
else
update(comp[{initial[i], {i, nxt}}], nxt - i + 1);
i = nxt;
}
};
intoBlocks(1, n, true);
int curCnt = n;
while (!s.empty()) {
while (!s.empty()) {
auto cur = prev(s.end())->second;
if (curCnt - cur.second + cur.first - 1 < n / 2) break;
curCnt -= cur.second - cur.first + 1;
s.erase(prev(s.end()));
}
if (curCnt == n / 2)
s.clear();
else if (!s.empty()) {
auto cur = prev(s.end());
int mid = cur->second.second - curCnt + n / 2;
intoBlocks(cur->second.first, mid, true);
intoBlocks(mid + 1, cur->second.second, true);
s.erase(cur);
}
}
for (auto& i : allBlocks) invComp.push_back(i);
cnt = invComp.size() - 1;
for (int i = 1; i <= cnt; ++i) comp[invComp[i]] = i;
vector<pair<int, pair<int, int>>> queries;
for (int i = 0; i < q; ++i) {
int t, x;
cin >> t >> x;
queries.push_back({t, {i, x}});
}
sort(queries.begin(), queries.end());
vector<int> res(q);
tree.assign(cnt + 1, 0);
intoBlocks(1, n);
int idx = 0;
curCnt = n;
for (int i = 0; i < n && idx < q && !s.empty(); ++i) {
while (idx < q && queries[idx].first == i) {
auto [curQ, curCard] = queries[idx++].second;
int groupIdx = query(curCard);
int preSum = sum(groupIdx),
initialIdx = invComp[groupIdx].second.second;
for (; preSum > curCard; --preSum, --initialIdx);
res[curQ] = initial[initialIdx];
}
while (!s.empty()) {
auto cur = prev(s.end())->second;
if (curCnt - cur.second + cur.first - 1 < n / 2) break;
curCnt -= cur.second - cur.first + 1;
s.erase(prev(s.end()));
}
if (curCnt == n / 2)
s.clear();
else if (!s.empty()) {
auto cur = prev(s.end());
update(comp[*cur], cur->second.first - cur->second.second - 1);
int mid = cur->second.second - curCnt + n / 2;
intoBlocks(cur->second.first, mid, false);
intoBlocks(mid + 1, cur->second.second, false);
s.erase(cur);
}
}
while (idx < q) {
auto [curQ, curCard] = queries[idx++].second;
int groupIdx = query(curCard);
int preSum = sum(groupIdx),
initialIdx = invComp[groupIdx].second.second;
for (; preSum > curCard; --preSum, --initialIdx);
res[curQ] = initial[initialIdx];
}
for (auto& i : res) cout << i << '\n';
return 0;
}
