左偏树

#include <bits/stdc++.h>
using namespace std;
int fa[100005], lc[100005], rc[100005], a[100005], h[100005];
int n, m;

int find(int x)
{
    if(fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

int mergex(int x, int y)
{
    if(!x || !y) return x | y;
    if(a[x] > a[y]) swap(x, y);
    if(x > y && a[x] == a[y]) swap(x, y);
    rc[x] = mergex(rc[x], y);
    if(h[lc[x]] < h[rc[x]]) swap(lc[x], rc[x]);

    h[x] = h[rc[x]] + 1;

    return x;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    h[0] = -1;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        fa[i] = i;
    }

    int t, x, y;
    for(int i = 1; i <= m; i++)
    {
        cin >> t;
        if(t == 1)
        {
            cin >> x >> y;
            if(a[x] == -1 || a[y] == -1) continue;
            x = find(x);
            y = find(y);
            if(x == y) continue;
            fa[x] = fa[y] = mergex(x, y);
        }

        if(t == 2)
        {
            cin >> x;
            if(a[x] == -1) {
                cout << -1 << '\n';
                continue;
            }
            x = find(x);
            cout << a[x] << '\n';
            a[x] = -1;
            int lcx = lc[x], rcx = rc[x];
            fa[lcx] = lcx, fa[rcx] = rcx;
            fa[x] = mergex(lcx, rcx);
            if(rcx) fa[rcx] = fa[x];
            if(lcx) fa[lcx] = fa[x];
        }
    }
}