#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>
vl tree;
vl hranice;
vl nums;
ll velikost;
void update(ll l, ll L, ll R, ll c, ll i){
if (L == R){
tree[i] += c;
return;
}
ll mid = (L + R) / 2;
if (l <= mid) update(l, L, mid, c, 2*i + 1);
else update(l, mid+1, R, c, 2*i + 2);
tree[i] = tree[2*i + 1] + tree[2*i + 2];
}
ll secti(ll l, ll r, ll L, ll R, ll i){
if (r < L || R < l) return 0;
if (l <= L && R <= r) return tree[i];
ll mid = (L + R) / 2;
return secti(l, r, L, mid, 2*i + 1)
+ secti(l, r, mid+1, R, 2*i + 2);
}
ll target(ll t, ll i){
ll L = 0, R = velikost - 1;
ll pos = -1;
while (L < R) {
ll mid = (L + R) / 2;
ll leftSum = tree[2*i + 1];
if (leftSum < t) {
t -= leftSum;
pos = mid;
i = 2*i + 2;
L = mid + 1;
} else {
i = 2*i + 1;
R = mid;
}
}
return pos + 1;
}
void solve(ll l, ll r){
ll i = l;
while (i <= r){
ll j = min(hranice[i], r+1);
update(nums[i], 0, velikost-1, j - i, 0);
i = j;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, q;
cin >> n >> q;
nums.resize(n);
vl idx(n);
for (ll i = 0; i < n; i++){
ll num;
cin >> num;
num--;
nums[i] = num;
idx[num] = i;
}
for (velikost = 1; velikost < n; velikost *= 2);
tree.resize(2*velikost-1, 0);
hranice.resize(n, n);
vl st;
for (ll i = n-1; i >= 0; i--){
while (!st.empty() && nums[st.back()] < nums[i]) st.pop_back();
if (st.empty()){hranice[i] = n;} else hranice[i] = st.back();
st.push_back(i);
}
vector<vector<pl>> queries(n+1);
for (ll i = 0; i < q; i++){
ll t, b;
cin >> t >> b;
queries[min(t, n)].push_back({b-1, i});
}
vl ans(q);
for (auto &p : queries[0]){
ans[p.second] = nums[p.first];
}
solve(0, n/2 - 1);
solve(n/2, n-1);
for (ll i = 1; i <= n; i++){
for (auto p : queries[i]){
ll pos = p.first;
ll delka_bloku = target(pos+1, 0);
ll pref = secti(0, delka_bloku-1, 0, velikost-1, 0);
ll presah = pos - pref;
ans[p.second] = nums[idx[delka_bloku] + presah];
}
ll delka_pul = target(n/2 + 1, 0);
ll pref = secti(0, delka_pul-1, 0, velikost-1, 0);
ll L = (n/2 - pref) + idx[delka_pul];
ll R = (secti(0, delka_pul, 0, velikost-1, 0) - pref - 1) + idx[delka_pul];
solve(L, R);
update(delka_pul, 0, velikost-1, -(R - L + 1), 0);
}
for (ll i = 0; i < q; i++){
cout << ans[i] + 1 << "\n";
}
return 0;
}
