#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=2e5+10;
struct node{
	LL s[2],p,v,size,cnt;
	void init(int a,int b){
		v=a,p=b;
		size=1,cnt=1;
	}
}tr[N];
int root,idx;
void pushup(int u){
	tr[u].size=tr[tr[u].s[0]].size+tr[tr[u].s[1]].size+tr[u].cnt;	
}
void rotate(int u){
	int y=tr[u].p,z=tr[y].p;
	int k=tr[y].s[1]==u;
	tr[z].s[tr[z].s[1]==y]=u,tr[u].p=z;
	tr[y].s[k]=tr[u].s[k^1],tr[tr[u].s[k^1]].p=y;
	tr[u].s[k^1]=y,tr[y].p=u;
	pushup(y),pushup(u);
}
void splay(int u,int k){
	while(tr[u].p!=k){
		int y=tr[u].p,z=tr[y].p;
		if(z!=k){
			if((tr[y].s[0]==u)^(tr[z].s[0]==y))rotate(u);
			rotate(y);
		}
		rotate(u);
	}
	if(!k)root=u;
}
int get_k(int k){
	int u=root;
	while(u){
		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)k-=tr[tr[u].s[0]].size+tr[u].cnt,u=tr[u].s[1];	
		else return tr[u].v;
	}
	return -1;
}
void insert(LL v){
	int u=root,p=0;
	while(u&&tr[u].v!=v)p=u,u=tr[u].s[tr[u].v<v];
	if(u)tr[u].cnt++;
	else{
	    u=++idx;
	    if(p)tr[p].s[tr[p].v<v]=u;
	    tr[u].init(v,p);
	}
	splay(u,0);
}
int main(){
	int n,m;
	cin>>n>>m;
	insert(-1e10),insert(1e10);
	for(int i=1;i<=n;i++){
		LL a;
		cin>>a;
		insert(a);
	}
	while(m--){
		int op,k;
		cin>>op>>k;
		if(op==1){
			cout<<get_k(tr[root].size-k)<<endl;
		}
		else{
			insert(k);
		}
	}
	return 0;
}