#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(v) begin(v), end(v)
using namespace std;
using ll = long long;
template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }
class BinaryIndexedTree {
int n;
vector<int> dat;
public:
BinaryIndexedTree(int n_) : n(n_), dat(n_ + 1, 0) {}
void add(int k, ll x) {
++k;
while (k <= n) {
dat[k] += x;
k += k & -k;
}
}
ll sum(int k) const {
ll res = 0;
while (k > 0) {
res += dat[k];
k -= k & -k;
}
return res;
}
ll sum(int l, int r) const { return sum(r) - sum(l); }
ll get(int k) const { return sum(k, k + 1); }
template<class F> int max_right(F&& f) const {
int x = 0;
ll w = 0;
for (int k = 1 << 20; k > 0; k >>= 1) {
if (x + k <= n && f(w + dat[x + k])) {
w += dat[x + k];
x += k;
}
}
return x;
}
};
int main() {
int N, Q; cin >> N >> Q;
vector<int> A(N);
rep (i, N) cin >> A[i];
rep (i, N) --A[i];
int M = 2 * N;
vector<vector<pair<int, int>>> query(M);
vector<int> ans(Q, -1);
rep (i, Q) {
int t, k; cin >> t >> k;
chmin(t, M);
--k;
if (t == 0) ans[i] = A[k];
else query[t - 1].emplace_back(k, i);
}
vector<int> nxt(N, N); // 自分より大きい最初の要素
vector<int> len(N); // prefix で最大値を取るものについて、それが支配する区間の長さ
{
stack<int> st{{N}};
rrep (i, N) {
while (st.top() != N && A[st.top()] < A[i]) st.pop();
nxt[i] = st.top();
st.push(i);
}
while (st.top() != N) {
len[st.top()] = nxt[st.top()] - st.top();
st.pop();
}
}
vector<int> Arev(N);
rep (i, N) Arev[A[i]] = i;
BinaryIndexedTree bit(N);
rep (i, N) bit.add(A[i], len[i]);
for (auto qs : query) {
int a = bit.max_right([&](int w) { return w <= N / 2; });
int t = N / 2 - bit.sum(a);
a = Arev[a];
if (t) {
// A[a] が支配する区間が分割される
int l = a + len[a];
bit.add(A[a], t - len[a]);
len[a] = t;
a += t;
while (a < l) {
int na = min(nxt[a], l);
bit.add(A[a], na - a);
len[a] = na - a;
a = na;
}
}
for (auto [k, i] : qs) {
int a = bit.max_right([&](int w) { return w <= k; });
int t = k - bit.sum(a);
a = Arev[a];
ans[i] = A[a + t];
}
}
for (auto i : ans) cout << i + 1 << endl;
}
