#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];
int aib[200005];
void upd(int poz, int newv)
{
for(int i=poz;i<=n;i+=(i&(-i)))
aib[i] += newv;
}
int qry(int poz)
{
int aux=0;
for(int i=poz;i>0;i-=(i&(-i)))
aux += aib[i];
return aux;
}
int cautare_binara(int k)
{
int cur=0,initk=k;
for(int p=17;p>=0;p--)
{
if(cur + (1<<p) <= n && aib[cur + (1<<p)] < k)
{
k -= aib[cur + (1<<p)];
cur += (1<<p);
}
}
assert(qry(cur) < initk);
assert(qry(cur+1) >= initk);
return cur+1;
}
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];
}
assert(0);*/
int val_it = cautare_binara(poz);
int it = unde[val_it];
int pref = qry(val_it) - tori[it];
return a[it + (poz - pref) - 1];
}
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)
{
upd(a[poz], tori[poz]);
poz += tori[poz];
}
//afis();
for(int t=1;t<=MAXT;t++)
{
int val_mij = cautare_binara(n/2);
int pref = qry(val_mij);
int mij = unde[val_mij];
if(pref == n/2)
{
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;
}
upd(a[mij], -tori[mij]);
int oldri = mij + tori[mij];
tori[mij] = n/2 - (pref - tori[mij]);
upd(a[mij], +tori[mij]);
int cur = mij + tori[mij];
while(cur<oldri && a[cur] < a[mij])
{
if(cur + tori[cur] >= oldri)
tori[cur] = oldri - cur;
upd(a[cur], tori[cur]);
cur += tori[cur];
}
for(auto [poz,id]:qrys[t])
rez[id] = answer_qry(poz);
//afis();
}
assert(0);
}
