罗马皇帝很喜欢玩杀人游戏。
他的军队里面有n个人，每个人都是一个独立的团。最近举行了一次平面几何测试，每个人都得到了一个分数。
皇帝很喜欢平面几何，他对那些得分很低的人嗤之以鼻。他决定玩这样一个游戏。
它可以发两种命令：
1. Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人，那么就忽略该命令。
2. Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了，这条命令就忽略。
皇帝希望他每发布一条kill命令，下面的将军就把被杀的人的分数报上来。（如果这条命令被忽略，那么就报0分）

第一行一个整数n（1<=n<=1000000）。n表示士兵数，m表示总命令数。
第二行n个整数，其中第i个数表示编号为i的士兵的分数。（分数都是[0..10000]之间的整数）
第三行一个整数m(1<=m<=100000)
第3+i行描述第i条命令。命令为如下两种形式：
1. M i j
2. K i

如果命令是Kill，对应的请输出被杀人的分数。（如果这个人不存在，就输出0）

5
100 90 66 99 10
7
M 1 5
K 1
K 1
M 2 3
M 3 4
K 5
K 4

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 1001000

bool live[MAXN];

int L[MAXN],R[MAXN],V[MAXN],D[MAXN];

int uf[MAXN];

int get_fa(int now)

{

        return uf[now]==now ? now : uf[now]=get_fa(uf[now]);

}

int Merge(int x,int y)

{

        if (!x)return y;

        if (!y)return x;

        if (V[x]>V[y])swap(x,y);

        R[x]=Merge(R[x],y);

        if (D[L[x]]<D[R[x]])swap(L[x],R[x]);

        D[x]=D[R[x]]+;

        return x;

}

int main()

{

        freopen("input.txt","r",stdin);

        int x,y,z,n,m;

        scanf("%d",&n);

        for (int i=;i<=n;i++)uf[i]=i,live[i]=true;

        for (int i=;i<=n;i++)

        {

                scanf("%d ",V+i);

                D[i]=;

        }

        scanf("%d\n",&m);

        char opt;

        for (int i=;i<=m;i++)

        {

                scanf("%c",&opt);

                if (opt=='M')

                {

                        scanf("%d%d\n",&x,&y);

                        if (!live[x] || !live[y])continue;

                        if (get_fa(x)==get_fa(y))continue;

                        uf[get_fa(x)]=uf[get_fa(y)]=Merge(get_fa(x),get_fa(y));

                }else

                {

                        scanf("%d\n",&x);

                        if (!live[x])

                        {

                                printf("0\n");

                                continue;

                        }

                        int t;

                        live[t=get_fa(x)]=false;

                        uf[t]=Merge(L[t],R[t]);

                        uf[uf[t]]=uf[t];

                        printf("%d\n",V[t]);

                }

        }

}