#include <bits/stdc++.h>
using i64 = long long;
// #undef DEBUG
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(23)
#endif
constexpr int max_N = int(2E5) + 5;
constexpr int max_Q = int(1E6) + 5;
constexpr int LG = 19;
int N, Q;
int A[max_N];
int T[max_Q], I[max_Q], ans[max_Q];
int inv_p[max_N];
struct node {
int act, siz;
} tree[max_N << 2];
node unite(const node lhs, const node rhs) {
return {lhs.act + rhs.act, lhs.siz + rhs.siz};
}
void tree_build(int v, int l, int r) {
if (l == r) {
tree[v] = {0, 0};
return;
}
int mid = (l + r) >> 1;
tree_build(v << 1, l, mid);
tree_build(v << 1 | 1, mid + 1, r);
tree[v] = unite(tree[v << 1], tree[v << 1 | 1]);
}
void tree_build() {
tree_build(1, 0, N);
}
void tree_add(int v, int l, int r, int x, int y) {
if (l == r) {
tree[v] = {1, y};
return;
}
int mid = (l + r) >> 1;
if (x <= mid) {
tree_add(v << 1, l, mid, x, y);
} else {
tree_add(v << 1 | 1, mid + 1, r, x, y);
}
tree[v] = unite(tree[v << 1], tree[v << 1 | 1]);
}
void tree_add(int x, int y) {
tree_add(1, 0, N, x, y);
}
int tree_get_kth_act(int v, int l, int r, int k) {
if (l == r) {
return l;
}
int mid = (l + r) >> 1;
int left_act_size = tree[v << 1].act;
if (k < left_act_size) {
return tree_get_kth_act(v << 1, l, mid, k);
} else {
return tree_get_kth_act(v << 1 | 1, mid + 1, r, k - left_act_size);
}
}
int tree_get_kth_act(int k) {
return tree_get_kth_act(1, 0, N, k);
}
int tree_query(int v, int l, int r, int x) {
if (l == r) {
return 0;
}
int mid = (l + r) >> 1;
if (x <= mid) {
return tree_query(v << 1, l, mid, x);
} else {
return tree_query(v << 1 | 1, mid + 1, r, x) + tree[v << 1].siz;
}
}
int tree_query(int x) {
return tree_query(1, 0, N, x);
}
void debug_tree() {
#ifdef DEBUG
int n = tree[1].act;
for (int i = 0; i < n; ++i) {
int x = tree_get_kth_act(i);
std::cerr << x << ' ' << tree_query(x) << '\n';
}
#endif
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> N >> Q;
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
--A[i];
}
for (int i = 0; i < N; ++i) {
inv_p[A[i]] = i;
}
A[N] = N;
inv_p[N] = N;
debug("wtf");
std::vector<int> nxt_big(N), stk{N};
for (int i = N - 1; i >= 0; --i) {
while (A[i] > A[stk.back()]) {
stk.pop_back();
}
nxt_big[i] = stk.back();
stk.emplace_back(i);
}
debug("holyf");
tree_build();
debug("ok");
auto partition = [&](int l, int r) -> std::vector<int> {
debug(l, r);
std::vector<int> v;
while (l <= r) {
v.emplace_back(l);
l = std::min(r + 1, nxt_big[l]);
}
debug(v);
v.emplace_back(r + 1);
return v;
};
auto add = [&](std::vector<int> v) {
for (int i = 0; i + 1 < v.size(); ++i) {
debug(A[v[i]], inv_p[A[v[i + 1]]], inv_p[A[v[i]]]);
tree_add(A[v[i]], inv_p[A[v[i + 1]]] - inv_p[A[v[i]]]);
}
};
add(partition(0, N - 1));
tree_add(N, 0);
debug_tree();
auto get_kth = [&](int k) -> int {
int lo = 0, hi = tree[1].act - 1;
while (lo < hi) {
int mid = (lo + hi) >> 1;
int x = tree_get_kth_act(mid + 1);
int siz = tree_query(x);
if (k < siz) {
hi = mid;
} else {
lo = mid + 1;
}
}
int x = tree_get_kth_act(lo);
int siz = tree_query(x);
// debug(k, x, siz);
return A[inv_p[x] + k - siz];
};
auto group_kth = [&](int k) -> int {
int lo = 0, hi = tree[1].act - 1;
while (lo < hi) {
int mid = (lo + hi) >> 1;
int x = tree_get_kth_act(mid + 1);
int siz = tree_query(x);
if (k < siz) {
hi = mid;
} else {
lo = mid + 1;
}
}
int x = tree_get_kth_act(lo);
debug("group", k, tree_query(x));
return x;
};
#ifdef DEBUG
for (int i = 0; i < N; ++i) {
std::cerr << get_kth(i) + 1 << " \n"[i == N - 1];
}
#endif
for (int i = 0; i < Q; ++i) {
std::cin >> T[i] >> I[i];
--I[i];
T[i] = std::min(T[i], N);
}
std::vector<int> ord(Q);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) {
return T[lhs] < T[rhs];
});
int curq = 0;
std::vector<int> a(N);
for (int t = 0; curq < Q; ++t) {
while (curq < Q && T[ord[curq]] == t) {
ans[ord[curq]] = get_kth(I[ord[curq]]);
++curq;
}
int mid = get_kth(N / 2);
int g = group_kth(N / 2);
int size = tree_query(g + 1) - tree_query(g);
debug(t, mid, g, size);
if (g == mid) {
continue;
}
int left_size = inv_p[mid] - inv_p[g], right_size = size - left_size;
debug(left_size, right_size);
auto v = partition(inv_p[mid], inv_p[mid] + right_size - 1);
tree_add(g, inv_p[mid] - inv_p[g]);
add(v);
debug_tree();
debug();
#ifdef DEBUG
for (int i = 0; i < N; ++i) {
std::cerr << get_kth(i) + 1 << " \n"[i == N - 1];
}
#endif
}
for (int i = 0; i < Q; ++i) {
std::cout << ans[i] + 1 << '\n';
}
return 0;
}
