xdd的难题

233正在做xdd给233出的一道题，233看了看题。有n个数(1≤n≤1e6），然后每次输入一个x（1≤x≤1e5），有q（q<=1e4）个询问。看到这里的时候233眉头一皱，这.....
也许是个数据结构？凉了啊，233只会线段树。233给xdd说不行不行，不会做。xdd笑了笑，于是把x的范围改成了(1≤x≤1e3)。233说，行吧，那你要问啥。ffffffffold
走了过来，说这q个询问，有两种情况，一种是chakan x，查询第x大的是谁，另一种是gaibian x y把之前x位置上的数改成y。

233好像并不会这个题，表示难受的一批，所以233想请求你的帮忙，帮帮他好不好。

多组测试数据

每组测试数据

第一行一个n。
第二行 n个数。
第三行一个q。
从第四行起，每一行一个询问，一共有q个询问。

每次查询第x大，输出这个数

2
1 2
2
chakan 1
gaibian 1 2

2