#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,INF=1e12;
struct node{
	int s[2],v,p;
	int size,cnt;
	void init(int _v,int _p)
	{
		v=_v,p=_p;
		size=cnt=1;
	}
}tr[N];
int n,m;
int root,idx;
void pushup(int x)
{
	tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+tr[x].cnt;
}
void rotate(int x)
{
	int y=tr[x].p,z=tr[y].p;
	int k=(tr[y].s[1]==x);
	tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
	tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
	tr[x].s[k^1]=y,tr[y].p=x;
	pushup(y),pushup(x);
}
void splay(int x,int k)
{
	while(tr[x].p!=k)
	{
		int y=tr[x].p,z=tr[y].p;
		if(z!=k)
		{
			if((tr[y].s[1]==x)^(tr[z].s[1]==y)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
	if(!k) root=x; 
}
int insert(int v)
{
	int u=root,p=0;
	bool ok=false;
	while(u)
	{
		if(v==tr[u].v) {
			tr[u].cnt++;
			ok=true;
			break;
		}
		p=u,u=tr[u].s[v>tr[u].v];
	}
	if(!ok)
	{
		u=++idx;
		if(p) tr[p].s[v>tr[p].v]=u;
		tr[u].init(v,p);
	}
	splay(u,0);
	return u;
}
int get_k(int k)
{
	int u=root;
	while(true)
	{
		if(tr[tr[u].s[0]].size>=k) u=tr[u].s[0];
		else if(tr[tr[u].s[0]].size+tr[u].cnt>=k) return tr[u].v;
		else k-=tr[tr[u].s[0]].size+tr[u].cnt,u=tr[u].s[1];
	}
	return -1;
}
int main()
{
	cin>>n>>m;
	insert(-INF),insert(INF);
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		insert(x);
	}
	while(m--)
	{
		int op,x;
		cin>>op>>x;
		if(op==1) cout<<get_k(tr[root].size-x)<<endl;
		else insert(x);
	}
	return 0;
}