#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define md ((l + r) >> 1)
const int N = 200'005;
vector<array<int, 2>> ask[N];
int a[N], ans[1'000'005];
struct segtree {
int seg[1 << 19];
int n;
void build(int i, int l, int r) {
if (l == r) {
seg[i] = 0;
return;
}
build(i << 1, l, md);
build(i << 1 | 1, md + 1, r);
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
void init(int _n) {
n = _n;
build(1, 0, n - 1);
}
void upd(int i, int l, int r, int p, int x) {
if (l == r) {
seg[i] = x;
return;
}
if (p <= md) {
upd(i << 1, l, md, p, x);
} else {
upd(i << 1 | 1, md + 1, r, p, x);
}
seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
void upd(int i, int x) {
upd(1, 0, n - 1, i, x);
}
array<int, 2> get(int i, int l, int r, int p) {
if (l == r) {
return {l, p};
}
if (p < seg[i << 1]) {
return get(i << 1, l, md, p);
} else {
return get(i << 1 | 1, md + 1, r, p - seg[i << 1]);
}
}
array<int, 2> get(int p) {
return get(1, 0, n - 1, p);
}
int get2(int i, int l, int r, int p) {
if (l == r) {
return seg[i];
}
if (p <= md) {
return get2(i << 1, l, md, p);
} else {
return get2(i << 1 | 1, md + 1, r, p);
}
}
int get2(int p) {
return get2(1, 0, n - 1, p);
}
} seg;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, q;
cin >> n >> q;
int pos[n + 1];
for (int i = 0; i < n; i++) {
cin >> a[i];
pos[a[i]] = i;
}
for (int i = 0; i < q; i++) {
int t, p;
cin >> t >> p;
t = min(t, n);
ask[t].push_back({p - 1, i});
}
int nxt[n]{};
stack<int> st;
a[n] = 1e9;
st.push(n);
for (int i = n - 1; i >= 0; i--) {
while (a[i] > a[st.top()]) st.pop();
nxt[i] = st.top();
st.push(i);
}
seg.init(n + 1);
for (int i = 0; i < n; i = nxt[i]) {
seg.upd(a[i], nxt[i] - i);
}
bool isover = 0;
for (int j = 0; j <= n; j++) {
for (auto [p, idx] : ask[j]) {
auto [i, v] = seg.get(p);
ans[idx] = a[pos[i] + v];
}
if (isover) continue;
int cur = n / 2;
array<int, 2> V = seg.get(cur);
int i = pos[V[0]];
cur = V[1];
if (cur == 0) {
isover = 1;
continue;
}
int mx = i + seg.get2(a[i]);
seg.upd(a[i], cur);
cur = i + cur;
while (cur < n && seg.get2(a[cur]) == 0) {
int newcur = min(nxt[cur], mx);
seg.upd(a[cur], newcur - cur);
cur = newcur;
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
