#include <bits/stdc++.h>
using namespace std;
#define last(v) prev((v).end())
int N, Q;
vector<int> A, inv;
struct block {
int v, l, r, len; // l and r positions in relation to original deck A
block(int vv, int ll, int rr) {v = vv, l = ll, r = rr, len = r-l+1;}
bool operator<(const block &other) const {
return v < other.v;
}
};
set<block> deck;
vector<int> nxt;
vector<int> tree; // segtree indices in relation to values of A
void update(int v, int p, int tl = 0, int tr = N-1, int i = 1) {
if (tl == tr) {tree[i] = v; return ;}
int tm = (tl + tr) / 2;
if (p <= tm) update(v, p, tl, tm, i * 2);
else update(v, p, tm + 1, tr, i * 2 + 1);
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
int query(int k, int tl = 0, int tr = N-1, int i = 1) {
if (tl == tr) return A[inv[tl] + k];
int tm = (tl + tr) / 2;
if (k - tree[i * 2] >= 0) return query(k - tree[i * 2], tm + 1, tr, i * 2 + 1);
return query(k, tl, tm, i * 2);
}
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
cin >> N >> Q;
A.resize(N), nxt.resize(N), tree.resize(4*N), inv.resize(N);
for(int i = 0; i < N; i++) cin >> A[i];
for(int i = 0; i < N; i++) inv[A[i]-1] = i;
vector<vector<pair<int,int>>> ask(N+1);
vector<int> res(Q);
for(int i = 0; i < Q; i++) {
int t, p;
cin >> t >> p; p--;
ask[min(N, t)].push_back({p, i});
}
vector<int> stk = {N};
for(int i = N-1; i >= 0; i--) {
while(stk.size() > 1 && A[stk.back()] < A[i]) stk.pop_back();
nxt[i] = stk.back();
stk.push_back(i);
}
int cur = 0;
while(cur < N) {
deck.insert({A[cur], cur, nxt[cur]-1});
update(nxt[cur]-1 - cur + 1, A[cur]-1);
cur = nxt[cur];
}
int sz = N;
for(int t = 0; t <= N; t++) {
for(auto &[q, qi]: ask[t]) {
res[qi] = query(q);
}
while(sz - last(deck)->len >= N/2) sz -= last(deck)->len, deck.erase(last(deck));
block split = *last(deck);
deck.erase(last(deck));
deck.insert({split.v, split.l, split.r - (sz - N/2)});
update(split.r - (sz - N/2) - split.l + 1, A[split.l]-1);
int cur = split.r - (sz - N/2) + 1;
while(cur <= split.r) {
int r = min(split.r, nxt[cur]-1);
deck.insert({A[cur], cur, r});
update(r - cur + 1, A[cur]-1);
cur = nxt[cur];
}
}
for(int i = 0; i < Q; i++) cout << res[i] << '\n';
}
