#include <bits/stdc++.h>
using namespace std;
bool shuffle(vector <int> &nums) {
bool done = true;
int n = (int)nums.size();
for (int i = 0; i < n/2; i++) {
if (nums[i] > nums[n/2]) {
done = false;
break;
}
}
if (done)
return true;
vector <int> new_arr(n);
int p1 = 0, p2 = n/2;
int i = 0;
while (p1 < n/2 && p2 < n) {
if (nums[p1] < nums[p2]) {
new_arr[i++] = nums[p1++];
} else {
new_arr[i++] = nums[p2++];
}
}
while (p1 < n/2)
new_arr[i++] = nums[p1++];
while (p2 < n)
new_arr[i++] = nums[p2++];
nums = new_arr;
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
vector <int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
map <int, vector <pair <int, int>>> queries;
for (int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
queries[a].push_back({b, i});
}
int lst = 0;
bool done = false;
vector <int> ans(q);
for (auto i : queries) {
if (!done) {
for (int j = lst; j < i.first && !done; j++)
done |= shuffle(nums);
lst = i.first;
}
for (auto j : i.second)
ans[j.second] = nums[j.first-1];
}
for (int i = 0; i < q; i++)
cout << ans[i] << '\n';
}
