#include <bits/stdc++.h>
// #define int long long
using namespace std;
const int nmax = 2e6 + 1;
int v[nmax];
int ng[nmax];
int n;
void next_gr() {
stack<int> st;
for (int i = 1; i <= n; i++) {
while (!st.empty() && v[st.top()] < v[i]) {
ng[st.top()] = i;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
ng[st.top()] = n + 1;
st.pop();
}
}
void build(int l, int r, vector<pair<int, int>> &vv) {
while (l <= r) {
if (ng[l] - 1 < r) {
vv.push_back({l, ng[l] - 1});
l = ng[l];
} else {
vv.push_back({l, r});
return;
}
}
}
void build2(int l, int r, vector<array<int, 3>> &vv) {
while (l <= r) {
if (ng[l] - 1 < r) {
vv.push_back({v[l], l, ng[l] - 1});
l = ng[l];
} else {
vv.push_back({v[l], l, r});
return;
}
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int q, t;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
cin >> t;
if (t == 0) {
int a;
cin >> a;
cout << v[a] << '\n';
q--;
while (q--) {
cin >> t >> a;
cout << v[a] << '\n';
}
return 0;
}
next_gr();
vector<pair<int, int>> v1, v2;
build(1, n / 2, v1);
build(n / 2 + 1, n, v2);
set<array<int, 3>> s1, s2;
int iv1 = 0, iv2 = 0, sz1 = 0;
while (iv1 < v1.size() || iv2 < v2.size()) {
if (iv2 == v2.size() || (iv1 < v1.size() && v[v1[iv1].first] < v[v2[iv2].first])) {
if (sz1 < n / 2) {
sz1 += v1[iv1].second - v1[iv1].first + 1;
s1.insert({v[v1[iv1].first], v1[iv1].first, v1[iv1].second});
} else {
s2.insert({v[v1[iv1].first], v1[iv1].first, v1[iv1].second});
}
iv1++;
} else {
if (sz1 < n / 2) {
sz1 += v2[iv2].second - v2[iv2].first + 1;
s1.insert({v[v2[iv2].first], v2[iv2].first, v2[iv2].second});
} else {
s2.insert({v[v2[iv2].first], v2[iv2].first, v2[iv2].second});
}
iv2++;
}
}
/*cout << "s1:\n";
for (auto it : s1) {
cout << it[0] << " " << it[1] << " " << it[2] << '\n';
}
cout << "\ns2:\n";
for (auto it : s2) {
cout << it[0] << " " << it[1] << " " << it[2] << '\n';
}
cout << '\n';*/
for (int _ = 2; _ <= t; _++) {
vector<pair<int, int>> extra;
if (sz1 == n / 2) break;
while (sz1 > n / 2) {
auto [val, l, r] = *s1.rbegin();
s1.erase({val, l, r});
if (sz1 - (r - l + 1) >= n / 2) {
extra.push_back({l, r});
sz1 -= r - l + 1;
} else {
int cat_mai_trebe = sz1 - n / 2;
int rnou = r - cat_mai_trebe;
s1.insert({val, l, rnou});
extra.push_back({rnou + 1, r});
break;
}
}
vector<array<int, 3>> cur;
for (auto it : extra) {
build2(it.first, it.second, cur);
}
vector<array<int, 3>> pe1, pe2;
int s1rbegin = (*s1.rbegin())[0];
for (auto [val, l, r] : cur) {
if (s1rbegin > val) {
pe1.push_back({val, l, r});
} else {
pe2.push_back({val, l, r});
}
}
for (auto it : pe1) {
s1.insert(it);
}
for (auto it : pe2) {
s2.insert(it);
}/*
cout << "s1:\n";
for (auto it : s1) {
cout << it[0] << " " << it[1] << " " << it[2] << '\n';
}
cout << "s2\n";
for (auto it : s2) {
cout << it[0] << " " << it[1] << " " << it[2] << '\n';
}
cout << '\n';*/
}
// return 0;
vector<int> fin;
for (auto it : s1) {
for (int i = it[1]; i <= it[2]; i++) {
fin.push_back(v[i]);
}
}
for (auto it : s2) {
for (int i = it[1]; i <= it[2]; i++) {
fin.push_back(v[i]);
}
}
int a;
cin >> a;
cout << fin[a - 1] << '\n';
q--;
while (q--) {
cin >> t >> a;
cout << fin[a - 1] << "\n";
}
return 0;
}
