#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, q;
cin >> n >> q;
vector <int> a(n + 1), ans(q);
vector <ar <int, 2>> query[n + 1];
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int j = 0; j < q; j++) {
int t, i;
cin >> t >> i;
query[min(n, t)].push_back({i, j});
}
for (int j = 0; j <= n; j++) {
for (auto now : query[j])
ans[now[1]] = a[now[0]];
int l1 = 1, r1 = n / 2, l2 = r1 + 1, r2 = n;
vector <int> b = {0};
while (l1 <= r1 && l2 <= r2) {
if (a[l1] < a[l2]) {
b.emplace_back(a[l1++]);
} else {
b.emplace_back(a[l2++]);
}
}
while (l1 <= r1)
b.emplace_back(a[l1++]);
while (l2 <= r2)
b.emplace_back(a[l2++]);
swap(a, b);
}
for (int i : ans)
cout << i << '\n';
}
