抽象

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
struct node
{
	int lc,rc,dis,fa,s,id;bool flag;
}t[100005];
int m,n,rt;
int merge(int x,int y)
{
	if(!x||!y)return x+y;
	if(t[x].s>t[y].s||(t[x].s==t[y].s&&t[x].id>t[y].id))swap(x,y);
	t[x].rc=merge(t[x].rc,y);
	t[t[x].rc].fa=x;
	if(t[t[x].lc].dis<t[t[x].rc].dis)swap(t[x].lc,t[x].rc);
	t[x].dis=t[t[x].rc].dis+1;
	return x;
}
int find(int x)
{
	if(x==t[x].fa)return x;
	return t[x].fa=find(t[x].fa);
}
signed main()
{
	scanf("%d%d",&n,&m);
	t[0].dis=-1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&t[i].s);
		t[i].fa=i;
		t[i].flag=false;
		t[i].id=i;
	}
	for(int i=1;i<=m;i++)
	{
		int a,b,opt;
		scanf("%d%d",&opt,&a);
		if(opt==1)
		{
			scanf("%d",&b);
			if(t[a].flag==true||t[b].flag==true)continue;
			a=find(a);b=find(b);
			if(a!=b)t[a].fa=t[b].fa=merge(a,b);
		}
		else
		{
			if(t[a].flag==true)
			{
				cout<<-1<<endl;
				continue;
			}
			a=find(a);
			t[a].flag=true;
			cout<<t[a].s<<endl;
			t[t[a].lc].fa=t[a].fa=t[t[a].rc].fa=merge(t[a].lc,t[a].rc);
			t[a].lc=t[a].rc=0;
		}
	}
	return 0;
}