#include<bits/stdc++.h>
using namespace std;
const int MAXT = 3e5;
const int INF = 1e8;
int n,q;
int a[200005],tori[200005],unde[200005];
int rez[1000005];
vector<pair<int,int>> qrys[MAXT+5];
vector<int> comp[200005];
set<int> roots;
int answer_qry(int poz)
{
int pref=0;
for(auto val_it:roots)
{
int it = unde[val_it];
if(pref + tori[it] >= poz)
{
return a[it + (poz - pref) - 1];
}
pref += tori[it];
}
return -1;
//assert(0);
}
void afis()
{
for(auto it:roots) cout<<it<<" "<<tori[unde[it]]<<" roots\n";
cout<<"\n\n\n";
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
unde[a[i]] = i;
}
deque<int> dq;
for(int i=n;i>0;i--)
{
while(!dq.empty() && a[i] > a[dq.back()])
dq.pop_back();
if(dq.empty())
tori[i] = n+1 - i;
else
tori[i] = dq.back() - i;
dq.push_back(i);
}
for(int i=1;i<=q;i++)
{
int t,poz;
cin>>t>>poz;
if(t==0)
{
rez[i] = a[poz];
}
else
{
t = min(t, MAXT);
qrys[t].push_back({poz,i});
}
}
int poz=1;
while(poz<=n)
{
roots.insert(a[poz]);
poz += tori[poz];
}
//afis();
for(int t=1;t<=MAXT;t++)
{
int pref=0,mij=-1;
bool perfectly_split=0;
for(auto val_it:roots)
{
int it = unde[val_it];
pref += tori[it];
if(pref >= n/2)
{
if(pref==n/2)
perfectly_split=1;
mij = it;
break;
}
}
assert(mij!=-1);
if(perfectly_split)
{
for(int u=t;u<=MAXT;u++)
for(auto [poz,id]:qrys[u])
rez[id] = answer_qry(poz);
for(int i=1;i<=q;i++)
cout<<rez[i]<<"\n";
return 0;
}
int oldri = mij + tori[mij];
tori[mij] = n/2 - (pref - tori[mij]);
//cout<<a[mij]<<" "<<tori[mij]<<" mij & newtori\n";
int cur = mij + tori[mij];
while(cur<oldri && a[cur] < a[mij])
{
roots.insert(a[cur]);
//cout<<a[cur]<<" new root\n";
cur += tori[cur];
}
for(auto [poz,id]:qrys[t])
rez[id] = answer_qry(poz);
//afis();
}
assert(0);
}
