#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef long long ll;
#define int ll
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
vector<int> a(n);
for(int i=0;i<n;i++){
cin >> a[i]; a[i]--;
}
vector<int> t(q), id(q);
vector<int> p(q), res(q);
for(int i=0;i<q;i++){
cin >> t[i] >> id[i]; --id[i];
p[i] = i;
}
sort(p.begin(), p.end(), [&](int i, int j){
if(t[i] != t[j]) return t[i] < t[j];
else return id[i] < id[j];
});
int j = 0;
while(j < q && t[p[j]] == 0){
res[p[j]] = a[id[p[j]]];
j++;
}
vector<int> cnt(n), pos(n), par(n, n), ss;
for(int i=n-1;~i;i--){
pos[a[i]] = i;
while(!ss.empty() && a[ss.back()] < a[i]) ss.pop_back();
if(!ss.empty()) par[i] = ss.back();
ss.push_back(i);
}
{
int i = 0, m = n / 2;
while(i < m){
cnt[a[i]] = min(m, par[i]) - i;
i = par[i];
}
i = m;
while(i < n){
cnt[a[i]] = par[i] - i;
i = par[i];
}
}
for(int i=1;i<=n;i++){
int sum = 0, P = -1, rem = 0;
for(int k=0;k<n;k++){
while(j < q && t[p[j]] == i && sum + cnt[k] > id[p[j]]){
res[p[j]] = a[pos[k] + (id[p[j]] - sum)];
j++;
}
sum += cnt[k];
if(sum >= n / 2 && P == -1){
rem = sum - n / 2;
P = k;
}
}
if(!rem){
break;
}
cnt[P] -= rem;
P = pos[P] + cnt[P];
int k = P; P += rem;
while(k < P){
cnt[a[k]] = min(P, par[k]) - k;
k = par[k];
}
}
sort(p.begin() + j, p.end(), [&](int i, int j){
return id[i] < id[j];
});
int sum = 0;
for(int k=0;k<n;k++){
while(j < q && sum + cnt[k] > id[p[j]]){
res[p[j]] = a[pos[k] + (id[p[j]] - sum)];
j++;
}
sum += cnt[k];
}
for(int i=0;i<q;i++){
cout<<++res[i]<<"\n";
}
}
