#include <bits/stdc++.h>
using namespace std;
int n, q;
int a[200000];
int pinv[200000];
int nxt[200000];
struct block {
int v;
int l, r;
int len;
block(int v, int l, int r) : v(v), l(l), r(r), len(r-l) {}
bool operator<(const block& o) const {
return v < o.v;
}
};
vector<int> queriesPerT[200001];
map<pair<int, int>, int> answers;
int st[800000];
void st_set(int n, int tl, int tr, int pos, int val) {
if (tl == tr) {
st[n] = val;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm) st_set(2*n, tl, tm, pos, val);
else st_set(2*n+1, tm+1, tr, pos, val);
st[n] = st[2*n] + st[2*n+1];
}
int query(int k) {
int node = 1, tl = 0, tr = n-1;
while (tl != tr) {
int tm = (tl + tr) / 2;
if (st[2*node] > k) {
node = 2*node;
tr = tm;
} else {
k -= st[2*node];
node = 2*node+1;
tl = tm+1;
}
}
return a[pinv[tl] + k];
}
int main() {
cin >> n >> q;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) pinv[a[i]-1] = i;
vector<pair<int, int>> queries;
for (int i = 0; i < q; i++) {
int t, k;
cin >> t >> k;
k--;
t = min(t, n);
queriesPerT[t].push_back(k);
queries.push_back({t, k});
}
stack<int> st;
st.push(n);
for (int i = n-1; i >= 0; i--) {
while (st.size() > 1 && a[st.top()] < a[i]) st.pop();
nxt[i] = st.top();
st.push(i);
}
set<block> blocks;
int p = 0;
while (p < n) {
int r = nxt[p];
blocks.insert({a[p], p, r});
st_set(1, 0, n-1, a[p]-1, r-p);
p = r;
}
int sz = n;
for (int t = 0; t <= n; t++) {
for (int k: queriesPerT[t]) {
answers[make_pair(t, k)] = query(k);
}
while (sz - blocks.rbegin()->len >= n/2) {
sz -= blocks.rbegin()->len;
blocks.erase(--blocks.end());
}
block b = *blocks.rbegin();
blocks.erase(--blocks.end());
blocks.insert({b.v, b.l, b.r - (sz - n/2)});
st_set(1, 0, n-1, a[b.l]-1, b.r - (b.l + (sz - n/2)));
int p = b.r - (sz - n/2);
while (p < b.r) {
int r = min(nxt[p], b.r);
blocks.insert({a[p], p, r});
st_set(1, 0, n-1, a[p]-1, r-p);
p = r;
}
}
for (auto q: queries) {
cout << answers[q] << "\n";
}
}
