#include <bits/stdc++.h>
inline char getch(){
    static char buf[1 << 20], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1 ++;
}
inline bool cmp(register signed x, register signed y){
    return y-x>>31;
}
inline bool cmp(register long long x,register long long y){
	return y-x>>63;
}
inline int read(){
    register int x (0);
    register char c (getchar());
    while(cmp(48,c) | cmp(c,57)) c = getchar();
    while((cmp(48,c)^1) & (cmp(c,57)^1)) {x = (x<<1) + (x<<3) + (c^48),c = getchar();}
    return x;
}
inline void write(int i){
    if(i > 9)write(i / 10) ;
    putchar((i-i/10*10) | 0x30) ;
}
#define mx 100005
#define rep(i,l,r) for(register int i(l);i<=r;++i)
#define per(i,r,l) for(register int i(r);i>=l;--i)
using namespace std;
int n=read(),m=read(),fa[mx],l[mx],r[mx],val[mx],dis[mx];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int merge(int x,int y){
    if(!x||!y)return x|y;
    if(val[x]>val[y])swap(x,y);
    r[x]=merge(r[x],y);
    if(dis[r[x]]<dis[l[x]])swap(l[x],r[x]);
    dis[x]=dis[r[x]]+1;
    fa[l[x]]=fa[r[x]]=fa[x]=x;
    return x;
}
inline int pop(int x){
    val[x]=-1,fa[l[x]]=l[x],fa[r[x]]=r[x],fa[x]=merge(l[x],r[x]);
    return 0;
}
signed main(){
    rep(i,1,n)fa[i]=i,val[i]=read();
    int op,x,y;
    while(m--){
        op=read(),x=read();
        if(op==1){
            y=read();
            if(val[x]==-1||val[y]==-1)continue;
            x=find(x),y=find(y);
            if(x!=y)fa[x]=fa[y]=merge(x,y);
        }
        else{
            if(val[x]==-1)putchar('-'),putchar('1'),putchar('\n');
            else write(val[find(x)]),putchar('\n'),pop(find(x));
        }
    }
    return 0;
}

提交记录