#include <bits/stdc++.h>
using namespace std;
struct fenwick {
int size, logn;
vector<int> fenw;
fenwick(int n) : size(n), logn(__lg(n)), fenw(n + 1) {}
void add(int i, int v) {
for (i++; i <= size; i += i & -i) {
fenw[i] += v;
}
}
int query(int r) {
int ans = 0;
for (; r > 0; r -= r & -r) {
ans += fenw[r];
}
return ans;
}
int lower_bound(int s) {
int pos = 0;
for (int delta = 1 << logn; delta > 0; delta /= 2) {
if (pos + delta <= size && fenw[pos + delta] < s) {
pos += delta;
s -= fenw[pos];
}
}
return pos;
}
};
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int &v : a) {
cin >> v;
v--;
}
int X = n;
vector<vector<pair<int, int>>> queries(X);
for (int i = 0; i < q; i++) {
int t, p;
cin >> t >> p;
p--, t = min(t, X - 1);
queries[t].emplace_back(i, p);
}
vector<int> nxt(n);
stack<int> st;
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && a[st.top()] < a[i]) {
st.pop();
}
nxt[i] = st.empty() ? n : st.top();
st.push(i);
}
vector<int> answer(q);
for (auto [i, p] : queries[0]) {
answer[i] = a[p];
}
fenwick fenw(n);
vector<int> l(n), r(n);
int pos = 0;
while (pos != n) {
int go = nxt[pos];
if (pos < n / 2 && go > n / 2) {
go = n / 2;
}
l[a[pos]] = pos;
r[a[pos]] = go;
fenw.add(a[pos], go - pos);
pos = go;
}
for (int t = 1; t < X; t++) {
for (auto [i, p] : queries[t]) {
int j = fenw.lower_bound(p + 1);
int sum = fenw.query(j + 1);
answer[i] = a[r[j] - (sum - p)];
}
int j = fenw.lower_bound(n / 2);
int sum = fenw.query(j + 1);
if (sum != 0) {
int first = r[j] - (sum - n / 2), right = r[j];
fenw.add(j, first - r[j]);
r[j] = first;
while (first != right) {
int go = min(right, nxt[first]);
l[a[first]] = first;
r[a[first]] = go;
fenw.add(a[first], go - first);
first = go;
}
}
}
for (int v : answer) {
cout << 1 + v << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
