蒟蒻连左偏树板子都能打挂（QAQ，求调，玄关。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct N{
	int val,dist,fa,l,r;
}a[100005];
bool d[100005];
int find(int x)
{
	if(a[x].fa==x) return x;
	return a[x].fa=find(a[x].fa);
}
int merge(int x,int y)
{
	if(!x||!y) return x|y;
	if(a[x].val>a[y].val) swap(x,y);
	a[x].r=merge(a[x].r,y);
	if(a[a[x].r].dist>a[a[x].l].dist) swap(a[x].l,a[x].r);
	a[x].dist=a[a[x].r].dist+1;
	return x;
}
int query(int x)
{
	return a[(x=find(x))].val;
}
void del(int x)
{
	x=find(x);
	a[a[x].l].fa=a[x].l,a[a[x].r].fa=a[x].r;
	a[a[x].l].fa=a[a[x].r].fa=merge(a[x].l,a[x].r);
	d[x]=true;
	a[x]={0,0,a[a[x].l].fa,0,0};
}
signed main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	cin.tie(0);
	cout.tie(0);
	int n,m,op,x,y;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i].val,a[i].dist=1,a[i].fa=i;
	while(m--)
	{
		cin>>op>>x;
		if(op==1)
		{
			cin>>y;
			if(d[x]||d[y]) continue;
			x=find(x),y=find(y);
			if(x!=y) a[x].fa=a[y].fa=merge(x,y);
		}
		if(op==2)
			if(d[x]) cout<<-1<<"\n";
			else cout<<query(x)<<"\n",del(x);
	}
	return 0;
}