P1007

罗马游戏

罗马游戏

罗马皇帝很喜欢玩杀人游戏。他的军队中有 nn 名士兵，初始时每名士兵各自组成一个独立的团。最近，军队举行了一次平面几何测试，每名士兵都获得了一个分数。皇帝十分喜欢平面几何，并对得分较低的士兵嗤之以鼻，因此决定进行如下游戏。

皇帝可以发布两种命令：

  1. M i j：将士兵 ii 所在的团与士兵 jj 所在的团合并。如果士兵 ii 或士兵 jj 已经死亡，则忽略该命令。
  2. K i：杀死士兵 ii 所在团中分数最低的士兵。如果士兵 ii 已经死亡，则忽略该命令。

每当皇帝发布一条 K 命令，将军都需要报告被杀士兵的分数。如果该命令被忽略，则报告 00。

输入格式

第一行包含一个整数 nn，表示士兵人数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n，其中 aia_i 表示编号为 ii 的士兵的分数。所有士兵的分数两两不同。

第三行包含一个整数 mm，表示命令总数。

接下来的 mm 行中，第 ii 行描述第 ii 条命令。命令为以下两种形式之一：

  • M i j；
  • K i。

输出格式

对于每条 K 命令，输出一行一个整数，表示被杀士兵的分数。如果该命令被忽略，则输出 00。

样例输入

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

样例输出

10
100
0
66

数据范围

  • 1≤n≤1061\le n\le 10^6；
  • 1≤m≤1051\le m\le 10^5；
  • 所有士兵的分数两两不同。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

10
100
0
66