2623 问题 D: 罗马游戏

 时间限制: 2s 内存限制: 128MB
题目描述

罗马皇帝很喜欢玩杀人游戏。 他的军队里面有n个士兵，每个士兵都是一个独立的团。最近举行了一次平面几何测试，每个士兵都得到了一个分数。 皇帝很喜欢平面几何，他对那些得分很低的士兵嗤之以鼻。

他决定玩这样一个游戏。 它可以发两种命令：

M i j 把i所在的团和j所在的团合并成一个团。如果i,j有一个士兵是死人那么就忽略该命令。
K i 把i所在的团里面得分最低的士兵杀死。如果i这个士兵已经死了，这条命令就忽略。

皇帝希望他每发布一条 K i 命令，下面的将军就把被杀的士兵的分数报上来 （如果这条命令被忽略，那么就报0分）。

保证士兵的分数互不相同。

输入

第一行一个整数n，表示士兵数。

第二行n个整数a1,a2,…an，其中ai表示编号为i的士兵的分数。

第三行一个整数m。

第3+i行描述第i条命令。命令为如下两种形式：M i j 或 K i。

输出

如果命令是 K i，对应的请输出被杀士兵的分数（如果这个人不存在，就输出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

样例输出

10
100
0
66
提示

对于100%的数据，1≤n≤5×104，1≤m≤5×104，0≤ai≤107，注意测试数据中 M i j 的 i,j 可能在同一个团中。


                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            function setIframeHeight(iframe){if(iframe){iframe.height=iframe.contentWindow.document.getElementsByTagName("html")[0].offsetHeight}};$(document).ready(function(){$(window).resize(function(){setIframeHeight(document.getElementById("iframe0"))})});
                        

                    

                

                

                    

                        
比赛状况