我就是不用左偏树和平衡树！玄关求条（

#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <functional>
using namespace std;
inline void read(int &x)
{
	char c=getchar();x=0;
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10-48+c,c=getchar();
}
int n,m,opt,u,v,a[100005];
bool kil[100005];
//SGT with Merging
#define mid (l+r>>1)
//1. SGT for pop the minimum-index number
struct SGT1
{
	int tr[3200005],top,ls[3200005],rs[3200005];
	bool lif[3200005];
	int mkn(){return ++top;}
	void upd(int now){tr[now]=tr[ls[now]]+tr[rs[now]];}
	void add(int now,int l,int r,int p,int k)
	{
		if(l==r) return tr[now]+=k,lif[now]=true,void();
		if(p<=mid)
		{
			if(!ls[now]) ls[now]=mkn();
			add(ls[now],l,mid,p,k);
		}
		else
		{
			if(!rs[now]) rs[now]=mkn();
			add(rs[now],mid+1,r,p,k);
		}
		upd(now);
	}
	void mrg(int &x,int y)
	{
		if(lif[x]&&lif[y]) return tr[x]+=tr[y],void();
		if(ls[y])
			if(ls[x]) mrg(ls[x],ls[y]);
			else ls[x]=ls[y];
		if(rs[y])
			if(rs[y]) mrg(rs[x],rs[y]);
			else rs[x]=rs[y];
		upd(x);
	}
	int qry(int now,int l,int r,int k) //return index
	{
		if(l==r) return l;
		if(k<=tr[ls[now]]) return qry(ls[now],l,mid,k);
		else return qry(rs[now],mid+1,r,k-tr[ls[now]]);
	}
}T1;
//2. SGT for searching k-smallest
int rut[100005];
struct SGT2
{
	struct node{int sz,rut;}tr[3200005];
	int top,ls[3200005],rs[3200005];
	bool lif[3200005];
	int mkn(){return ++top;}
	void upd(int now){tr[now].sz=tr[ls[now]].sz+tr[rs[now]].sz;}
	int add(int now,int l,int r,int p,int k)
	{
		if(l==r)
		{
			if(!tr[now].rut) tr[now].rut=T1.mkn();
			T1.add(tr[now].rut,1,n,p,k);
			tr[now].sz+=k;lif[now]=true;
			return tr[now].rut;
		}
		int ret;
		if(a[p]<=mid)
		{
			if(!ls[now]) ls[now]=mkn();
			ret=add(ls[now],l,mid,p,k);
		}
		else
		{
			if(!rs[now]) rs[now]=mkn();
			ret=add(rs[now],mid+1,r,p,k);
		}
		upd(now);return ret;
	}
	void mrg(int &x,int y)
	{
		if(lif[x]&&lif[y]) return tr[x].sz+=tr[y].sz,T1.mrg(tr[x].rut,tr[y].rut),void();
		if(ls[y])
			if(ls[x]) mrg(ls[x],ls[y]);
			else ls[x]=ls[y];
		if(rs[y])
			if(rs[x]) mrg(rs[x],rs[y]);
			else rs[x]=rs[y];
		upd(x);
	}
	int qry(int now,int l,int r,int k)
	{
		if(l==r) return tr[now].rut;
		if(k<=tr[ls[now]].sz) return qry(ls[now],l,mid,k);
		else return qry(rs[now],mid+1,r,k-tr[ls[now]].sz);
	}
	int fnd(int now,int l,int r,int k)
	{
		if(!now) return 0;
		if(l==r) return l;
		if(k<=tr[ls[now]].sz) return fnd(ls[now],l,mid,k);
		else return fnd(rs[now],mid+1,r,k-tr[ls[now]].sz);
	}
}T2;
//UFS
int fa[100005];
int qry(int x){return (x^fa[x])?fa[x]=qry(fa[x]):x;}
//DCT
int tcd[100005],nn;
int main()
{
//	freopen("P3377_1.in","r",stdin);
//	freopen("P3377_1.ans","w",stdout);
//	Other Initials
	read(n);read(m);tcd[0]=-1;
	for(int i=1;i<=n;i++) read(a[i]),tcd[i]=a[i],fa[i]=i;
	sort(tcd+1,tcd+n+1);nn=unique(tcd+1,tcd+n+1)-tcd-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(tcd+1,tcd+nn+1,a[i])-tcd;
//	SGT Initials
	for(int i=1;i<=n;i++) T2.add(rut[i]=T2.mkn(),1,nn,i,1);
//	Address
	while(m--)
	{
		read(opt);read(u);
		if(opt==1)
		{
			read(v);
			if(kil[u]||kil[v]) continue;
			int ru=qry(u),rv=qry(v);
			if(ru^rv) fa[ru]=rv,T2.mrg(rut[rv],rut[ru]);
		}
		else
		{
			int ru,ans;
			if(kil[u]) ans=0;
			else
			{
				ru=qry(u);
				ans=T2.fnd(rut[ru],1,nn,1);
			}
			printf("%d\n",tcd[ans]);
			if(ans>0)
			{
				ans=T2.qry(rut[ru],1,nn,1);
				ans=T1.qry(ans,1,n,1);
//				cout<<"Popped "<<ans<<endl;
				T2.add(rut[ru],1,nn,ans,-1);
				kil[ans]=true;
			}
		}
	}
	return 0;
}