#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 200000;
constexpr int B = 300;
struct DataStructure {
int n;
std::vector<int> a;
std::vector<int> nxt;
std::vector<std::pair<int, int>> blocks;
std::deque<std::pair<int, int>> d[N / B + 2];
int siz[N / B + 2];
bool FirstTime;
DataStructure(std::vector<int> a, std::vector<int> nxt, std::vector<std::pair<int, int>> blocks) : n(a.size()), a(a), nxt(nxt), blocks(blocks) {
FirstTime = true;
memset(siz, 0, sizeof siz);
}
int at(int p) {
if (FirstTime) {
return a[p];
}
int cursiz = 0;
for (int cur = 0; ; cur++) {
if (cursiz + siz[cur] > p) {
int id = 0;
for (auto [l, r] : d[cur]) {
cursiz += r - l;
if (cursiz > p) {
cursiz -= r - l;
return a[l + p - cursiz];
}
id++;
}
}
cursiz += siz[cur];
}
}
void insert(int L, int R) {
//~ std::cerr << "Divided: " << L << " " << R << "\n";
for (int cur = 0; ; cur++) {
if (d[cur + 1].empty() || a[d[cur + 1][0].first] > a[L]) {
int k = d[cur].size();
for (int i = 0; i <= k; i++) {
if (i == k || a[d[cur][i].first] > a[L]) {
d[cur].insert(d[cur].begin() + i, {L, R});
siz[cur] += R - L;
break;
}
}
while (d[cur].size() > B) {
int s = d[cur].back().second - d[cur].back().first;
siz[cur + 1] += s;
d[cur + 1].push_front(d[cur].back());
siz[cur] -= s;
d[cur].pop_back();
cur++;
}
break;
}
}
}
void nextShuffle() {
if (FirstTime) {
std::sort(blocks.begin(), blocks.end(), [&](const auto &i, const auto &j) {
return a[i.first] < a[j.first];
});
int cur = 0;
for (auto [l, r] : blocks) {
d[cur].push_back({l, r});
siz[cur] += r - l;
if (d[cur].size() == B) {
cur++;
}
}
FirstTime = false;
return;
}
int cursiz = 0;
int L = -1, R = -1;
int savecur = -1, saveid = -1;
for (int cur = 0; ; cur++) {
if (cursiz + siz[cur] > n / 2) {
int id = 0;
for (auto [l, r] : d[cur]) {
cursiz += r - l;
if (cursiz > n / 2) {
L = l;
R = r;
savecur = cur;
saveid = id;
break;
}
id++;
}
break;
}
cursiz += siz[cur];
}
//~ std::cerr << L << " " << R << "::\n";
cursiz -= R - L;
if (cursiz == n / 2) return;
int mid = n / 2 - cursiz + L;
// removal of the midBlock
siz[savecur] -= R - L;
d[savecur].erase(d[savecur].begin() + saveid);
for (int i = savecur + 1; !d[i].empty(); i++) {
//~ std::cerr << "Red flag\n";
int s = d[i].front().second - d[i].front().first;
siz[i - 1] += s;
d[i - 1].push_back(d[i].front());
siz[i] -= s;
d[i].pop_front();
}
// division of the midBlock
for (int i = L; i < mid; i = nxt[i]) {
insert(i, std::min(mid, nxt[i]));
}
for (int i = mid; i < R; i = nxt[i]) {
insert(i, std::min(R, nxt[i]));
}
//~ for (auto [l, r] : d[0]) {
//~ std::cout << l << " " << r << "\n";
//~ }
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
a[i]--;
}
std::vector<std::vector<std::pair<int, int>>> Q(n + 1);
std::vector<int> ans(q);
for (int i = 0; i < q; i++) {
int t, p;
std::cin >> t >> p;
t = std::min(t, n);
p--;
Q[t].push_back({p, i});
}
std::vector<int> nxt(n);
std::vector<int> st{n};
for (int i = n - 1; i >= 0; i--) {
while (st.back() < n && a[st.back()] < a[i]) {
st.pop_back();
}
nxt[i] = st.back();
st.push_back(i);
}
std::vector<std::pair<int, int>> blocks;
for (int i = 0; i < n / 2; i = nxt[i]) {
blocks.push_back({i, std::min(n / 2, nxt[i])});
}
for (int i = n / 2; i < n; i = nxt[i]) {
blocks.push_back({i, nxt[i]});
}
DataStructure D(a, nxt, blocks);
for (int t = 0; t <= n; t++) {
//~ std::cerr << "Stage " << t << ";\n";
for (auto [p, id] : Q[t]) {
ans[id] = D.at(p);
}
D.nextShuffle();
}
for (int i = 0; i < q; i++) {
std::cout << ans[i] + 1 << "\n";
}
return 0;
}
