#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void shuffle(vector<int> &a) {
int n = a.size();
vector<int> b;
int j = n / 2;
for (int i = 0; i < n / 2; i++) {
while (j < n && a[j] < a[i]) {
b.push_back(a[j++]);
}
b.push_back(a[i]);
}
for (int i = j; i < n; i++) {
b.push_back(a[i]);
}
swap(a, b);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
vector<int> A(N);
for (int &x : A) {
cin >> x;
}
if (N <= 1000 && 0) {
vector<vector<int>> T;
do {
T.push_back(A);
shuffle(A);
} while (A != T.back());
int M = T.size();
while (Q--) {
int t, i;
cin >> t >> i;
t = min(t, M - 1);
i--;
cout << T[t][i] << "\n";
}
return 0;
}
vector<int> q(Q);
int t;
for (auto &x : q) {
cin >> t >> x;
x--;
}
if (t == 0) {
for (int x : q) {
cout << A[x] << "\n";
}
return 0;
}
vector<int> f(N, N), stk;
for (int i = N - 1; i >= 0; i--) {
while (!stk.empty() && A[stk.back()] < A[i]) {
stk.pop_back();
}
if (!stk.empty()) {
f[i] = stk.back();
}
stk.push_back(i);
}
set<tuple<int, int, int>> s, s2;
for (int i = 0; i < N; i = f[i]) {
s.emplace(A[i], i, f[i]);
}
int T = N;
while (t--) {
while (1) {
auto [_, l, r] = *prev(s.end());
if (T - r + l < N / 2) {
break;
}
T -= r - l;
s2.insert(*prev(s.end()));
s.erase(prev(s.end()));
}
if (T == N / 2) {
break;
}
auto [v, l, r] = *prev(s.end());
s.erase(prev(s.end()));
int m = r - T + N / 2;
s.emplace(v, l, m);
for (int i = m; i < r; i = f[i]) {
s.emplace(A[i], i, min(r, f[i]));
}
}
s.insert(s2.begin(), s2.end());
vector<int> B;
for (auto [_, l, r] : s) {
B.insert(B.end(), A.begin() + l, A.begin() + r);
}
for (int x : q) {
cout << B[x] << "\n";
}
return 6/22;
}
