P2713 Roman Game

The Roman emperor enjoys a killing game. His army has $n$ soldiers, and each soldier initially forms an independent group. A recent plane geometry test was held, and each soldier received a score. The emperor loves plane geometry and despises soldiers with low scores. He decides to play the following game. He can issue two types of commands: - `M i j` Merge the groups containing $i$ and $j$ into one group. If either $i$ or $j$ is already dead, ignore this command. - `K i` Kill the lowest-scoring soldier in the group containing $i$. If soldier $i$ is already dead, ignore this command. After each `K i` command, the general should report the score of the soldier who was killed (if the command is ignored, report $0$). It is guaranteed that all soldiers’ scores are pairwise distinct.

The first line contains an integer $n$, the number of soldiers. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, where $a_i$ is the score of the soldier with index $i$. The third line contains an integer $m$. The $(3 + i)$-th line describes the $i$-th command, which is either `M i j` or `K i`.

For each `K i` command, output the score of the killed soldier (if such a person does not exist, output $0$).

Constraints: - For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le m \le 10^5$, $0 \le a_i \le 10^7$. Note: In the testdata, in the command `M i j`, $i$ and $j$ may already be in the same group. Translated by ChatGPT 5