#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const int N = 2e5 + 7, Q = 1e6 + 7;
int n, q;
int a[N], a_[N], res[Q], gr[N], fen[N];
pii g[N];
vector <pii> qu[Q];
void add(int x, int val) {for (; x < N; x += x & -x) fen[x] += val;}
int get(int x) {
int out = 0;
for (; x; x -= x & -x) out += fen[x];
return out;
}
int kth(int k) {
int sum = 0, x = 0;
for (int i = 17; i >= 0; i--) {
if (x+(1<<i) >= N) continue;
if (sum + fen[x+(1<<i)] <= k) {x += (1 << i); sum += fen[x];}
}
return x+1;
}
int main () {
FIO;
cin >> n >> q;
for (int i = 0; i < n; i++) cin >> a_[i];
for (int i = 0; i < q; i++) {
int t, x; cin >> t >> x; x--;
qu[min(n, t)].pb({x, i});
}
for (auto x : qu[0]) res[x.S] = a_[x.F];
for (int i = 0, n1 = 0, n2 = 0; i < n; i++) {
if (n2 == n/2 || (n1 < n/2 && a_[n1] < a_[n/2+n2])) a[i] = a_[n1++];
else a[i] = a_[n/2+n2++];
}
for (auto x : qu[1]) res[x.S] = a[x.F];
stack <int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) {
gr[a[st.top()]] = i;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
gr[a[st.top()]] = n;
st.pop();
}
for (int i = 0; i < n; i = gr[a[i]]) {
g[a[i]] = {i, gr[a[i]]-1};
add(a[i], gr[a[i]]-i);
}
for (int i = 2; i <= n; i++) {
int x = kth(n/2);
int y = get(x-1);
if (y < n/2) {
int l = g[x].F, r = g[x].S;
add(x, n/2-y-r+l-1);
l += n/2-y;
g[x].S = l-1;
for (int j = l; j <= r; j = gr[a[j]]) {
add(a[j], min(r+1, gr[a[j]])-j);
g[a[j]] = {j, min(r, gr[a[j]]-1)};
}
}
for (auto z : qu[i]) {
int h = kth(z.F);
res[z.S] = a[g[h].F+z.F-get(h-1)];
}
}
for (int i = 0; i < q; i++) cout << res[i] << "\n";
return 0;
}
