#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,q;
int a[maxn];
int t[maxn],x[maxn];
vector<int> v[maxn];
int ans[maxn];
int op[maxn];
void read()
{
cin>>n>>q;
for(int i=1; i<=n; i++)
{
cin>>a[i];
op[a[i]]=i;
}
for(int i=1; i<=q; i++)
{
cin>>t[i]>>x[i];
v[min(n,t[i])].push_back(i);
if(t[i]==0)ans[i]=a[x[i]];
}
}
struct group
{
int id;
group() {}
group(int _id)
{
id=_id;
}
bool operator<(const group&g)const
{
return a[id]<a[g.id];
}
};
set<group> s;
int sz[maxn],nxt[maxn];
int tr[800001];
void upd(int i,int l,int r,int id,int vl)
{
if(l==r)
{
//cout<<"in "<<l<<" "<<vl<<endl;
tr[i]=vl;
return;
}
int m=(l+r)/2;
if(id<=m)upd(i*2,l,m,id,vl);
else upd(i*2+1,m+1,r,id,vl);
tr[i]=tr[i*2]+tr[i*2+1];
}
pair<int,int> query(int i,int l,int r,int x,int bf)
{
if(l==r)return {bf+tr[i],l};
int m=(l+r)/2;
if(tr[i*2]>=x)return query(i*2,l,m,x,bf);
return query(i*2+1,m+1,r,x-tr[i*2],bf+tr[i*2]);
}
void prec()
{
stack<int> h;
for(int i=n; i>=1; i--)
{
while(h.size()&&a[h.top()]<a[i])h.pop();
if(h.size())nxt[i]=h.top();
else nxt[i]=n+1;
h.push(i);
}
int i=1;
while(i<=n)
{
sz[i]=nxt[i]-i;
upd(1,1,n,a[i],sz[i]);
s.insert({i});
i=nxt[i];
}
}
void solve()
{
int br=-1;
int cnt=0;
auto it=s.begin();
while(cnt<n/2)
{
cnt+=sz[it->id];
if(cnt>n/2)br=it->id;
else if(cnt<n/2)it++;
}
if(br==-1)
{
for(int lp=1;lp<=n;lp++)
{
for(int i=0; i<v[lp].size(); i++)
{
int idx=x[v[lp][i]];
pair<int,int> h=query(1,1,n,idx,0);
//cout<<idx<<" ? "<<h.first<<" "<<op[h.second]<<" "<<sz[op[h.second]]<<endl;
ans[v[lp][i]]=a[op[h.second]+sz[op[h.second]]-1-(h.first-idx)];
}
}
}
//cout<<"here"<<endl;
/*for(int i=1;i<=n;i++)
cout<<nxt[i]<<endl;
cout<<endl;*/
int lp=0;
while(br!=-1)
{
lp++;
it=s.find({br});
group g=*it;
int rt=br+sz[br];
int bf=cnt-sz[g.id];
int nid=n/2-bf+g.id;
while(nid<rt)
{
sz[nid]=min(rt,nxt[nid])-nid;
upd(1,1,n,a[nid],sz[nid]);
s.insert({nid});
nid=nxt[nid];
}
s.erase({br});
sz[br]=n/2-bf;
upd(1,1,n,a[br],sz[br]);
s.insert({br});
it=s.find(br);
while(cnt>n/2)
{
cnt-=sz[it->id];
if(cnt==n/2)br=-1;
else if(cnt<n/2)br=it->id;
else it--;
}
for(int i=0; i<v[lp].size(); i++)
{
int idx=x[v[lp][i]];
pair<int,int> h=query(1,1,n,idx,0);
//cout<<idx<<" ? "<<h.first<<" "<<op[h.second]<<" "<<sz[op[h.second]]<<endl;
ans[v[lp][i]]=a[op[h.second]+sz[op[h.second]]-1-(h.first-idx)];
}
if(br!=-1)cnt+=sz[br];
else
{
while(lp<n)
{
lp++;
for(int i=0; i<v[lp].size(); i++)
{
int idx=x[v[lp][i]];
pair<int,int> h=query(1,1,n,idx,0);
//cout<<idx<<" ? "<<h.first<<" "<<op[h.second]<<" "<<sz[op[h.second]]<<endl;
ans[v[lp][i]]=a[op[h.second]+sz[op[h.second]]-1-(h.first-idx)];
}
}
}
}
for(int i=1; i<=q; i++)
cout<<ans[i]<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
read();
prec();
solve();
return 0;
}
/*
10 0
3 2 7 5 4 6 1 8 9 10
*/
/*
8 8
5 2 7 3 1 6 8 4
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
8 8
5 2 7 3 1 6 8 4
3 1
1
3 2
6
3 3
5
3 4
2
3 5
7
3 6
3
3 7
8
3 8
4
10 10
3 2 5 1 8 9 10 4 7 6
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
*/
