#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
using VI = vector<int>;
const int NN = 2e5 + 4;
struct BIT {
int C[NN];
void add(int x, int v) {
while (x < NN) C[x] += v, x += x & -x;
}
int sum(int x) {
int ret = 0;
while (x) ret += C[x], x -= x & -x;
return ret;
}
int kth(int x) {
int pos = 0;
for (int i = 17; i >= 0; i--)
if (pos + (1 << i) < NN && C[pos + (1 << i)] < x)
pos += (1 << i), x -= C[pos];
return pos + 1;
}
};
BIT S;
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n, q;
cin >> n >> q;
VI a(n), rev(n + 1), ans(q);
vector<vector<pi>> v(n + 1);
for (int i = 0; i < n; i++) cin >> a[i], rev[a[i]] = i;
for (int i = 0, t, x; i < q; i++) {
cin >> t >> x, t = min(t, n);
if (t == 0)
ans[i] = a[x - 1];
else
v[t].emplace_back(x - 1, i);
}
VI nxt(n), ds(n + 1);
auto SetVal = [&](int x, int v) { S.add(x, v - ds[x]), ds[x] = v; };
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && a[j] < a[i]) j++;
SetVal(a[i], j - i), i = j;
}
VI v2;
for (int i = n - 1; i >= 0; i--) {
while (!v2.empty() && a[v2.back()] < a[i]) v2.pop_back();
if (!v2.empty())
nxt[i] = v2.back();
else
nxt[i] = n;
v2.push_back(i);
}
for (int i = 1; i <= n; i++) {
int itf = S.kth(n / 2 + 1), its = ds[itf], sum = S.sum(itf - 1);
if (sum < n / 2) {
int l = rev[itf], r = l + its;
SetVal(a[l], n / 2 - sum);
l += n / 2 - sum;
for (int i = l; i < r; i = nxt[i]) SetVal(a[i], min(r, nxt[i]) - i);
}
for (auto p : v[i]) {
int pos = p.first, idx = p.second, qos = S.kth(pos + 1),
sum = S.sum(qos - 1);
ans[idx] = a[rev[qos] + pos - sum];
}
}
for (int x : ans) cout << x << "\n";
}
