#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int N = 1e6 + 10;
int n, q;
int a[N], ans[N], nxt[N], rev_a[N], ed[N];
vector<pair<int, int> > query[N];
int T[N << 2];
void up(int s, int l, int r, int pos, int val) {
if (l == r) {
T[s] = val;
return;
}
int mid = l + r >> 1;
if (pos <= mid) up(s << 1, l, mid, pos, val);
else up(s << 1 | 1, mid + 1, r, pos, val);
T[s] = T[s << 1] + T[s << 1 | 1];
}
int get(int s, int l, int r, int from, int to) {
if (l > to || r < from) return 0;
if (from <= l && r <= to) return T[s];
int mid = l + r >> 1;
return get(s << 1, l, mid, from, to) + get(s << 1 | 1, mid + 1, r, from, to);
}
int walk_on_tree (int s, int l, int r, int val) {
if (l == r) return l;
int mid = l + r >> 1;
if (T[s << 1] >= val) return walk_on_tree(s << 1, l, mid, val);
return walk_on_tree(s << 1 | 1, mid + 1, r, val - T[s << 1]);
}
int32_t main() {
#define task ""
cin.tie(0) -> sync_with_stdio(0);
if (fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
}
if (fopen(task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i], rev_a[a[i]] = i;
for(int i = 1; i <= q; i++) {
int t, x; cin >> t >> x;
query[min(n, t)].emplace_back(x, i);
}
// exit(0);
stack<int> st;
for(int i = n; i >= 1; i--) {
while (!st.empty() && a[st.top()] < a[i]) st.pop();
nxt[i] = st.empty() ? n + 1 : st.top();
st.push(i);
}
auto add = [&] (int start, int reach) {
int u = start;
while (u <= reach) {
ed[u] = min(nxt[u] - 1, reach);
up(1, 1, n, a[u], ed[u] - u + 1);
u = ed[u] + 1;
}
};
add(1, n);
for(int turn = 0, change = 1; turn <= n; turn++) {
for(auto [x, i] : query[turn]) {
int pos = walk_on_tree(1, 1, n, x);
int pre = get(1, 1, n, 1, pos - 1);
pos = rev_a[pos];
ans[i] = a[pos + x - pre - 1];
}
if (change == 0) continue;
int pos = walk_on_tree(1, 1, n, n / 2);
int pre = get(1, 1, n, 1, pos - 1);
pos = rev_a[pos];
if (pre + ed[pos] - pos + 1 == n / 2) {
change = 0;
continue;
}
int old = ed[pos];
ed[pos] = pos + n / 2 - pre - 1;
up(1, 1, n, a[pos], ed[pos] - pos + 1);
add(ed[pos] + 1, old);
}
for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}
