1 #include <cstdio> 2 #define LL long long 3 const LL Maxn=1000100; 4 struct Info{LL l,r,v,Dis;}Tree[Maxn]; 5 LL Father[Maxn],n,m,Dead[Maxn],u,v; 6 inline void Swap(LL &x,LL &y){LL t=x;x=y;y=t;} 7 LL Get(LL x) {return x==Father[x]?x:Father[x]=Get(Father[x]);} 8 LL Merge(LL u,LL v) 9 {10     if (u==0 || v==0) return u+v;11     if (Tree[u].v>Tree[v].v) Swap(u,v);12     Tree[u].r=Merge(Tree[u].r,v);13     if (Tree[Tree[u].l].Dis<Tree[Tree[u].r].Dis) 14         Swap(Tree[u].l,Tree[u].r);15     Tree[u].Dis=Tree[Tree[u].l].Dis+1;16     return u;17 }18 int main()19 {20     scanf("%lld",&n);21     for (LL i=1;i<=n;i++) scanf("%lld",&Tree[i].v),Tree[i].l=Tree[i].r=0;22     for (LL i=1;i<=n;i++) Father[i]=i;23     scanf("%lld",&m);24     for (LL i=1;i<=m;i++)25     {26         char ch=getchar();27         while (ch!=‘M‘ && ch!=‘K‘) ch=getchar();28         if (ch==‘M‘)29         {30             scanf("%lld%lld",&u,&v);31             LL fu=Get(u);32             LL fv=Get(v);33             if (fu==fv || Dead[u] || Dead[v]) continue;34             LL Tmp=Merge(fu,fv);35             Father[fu]=Father[fv]=Tmp;36         } 37         if (ch==‘K‘)38         {39             scanf("%lld",&u);40             if (Dead[u]) {puts("0"); continue;}41             LL fu=Get(u); Dead[fu]=true;42             printf("%lld\n",Tree[fu].v);43             LL Tmp=Merge(Tree[fu].l,Tree[fu].r);44             Father[fu]=Tmp;45             Father[Tmp]=Tmp;46         }47     }48     return 0;49 }