#P2343. 宝石管理系统

宝石管理系统

题目描述

GY 君购买了一批宝石放进了仓库。有一天 GY 君心血来潮,想要清点他的宝石,于是把 mm 个宝石都取出来放进了宝石管理系统。每个宝石 ii 都有一个珍贵值 viv_i,他希望你能编写程序查找到从大到小第 nn 珍贵的宝石。但是现在问题来了,他非常不小心的留了一些宝石在仓库里面,有可能要往现有的系统中添加宝石。这些宝石的个数比较少。他表示非常抱歉,但是还是希望你的系统能起作用。

输入格式

第一行两个整数 m,qm,q,表示已经取出来的宝石个数以及接下来的查询或插入操作个数。

第二行 mm 个正整数,表示这 mm 个宝石的珍贵值。

以下 qq 行,每行两个整数 c,nc,n

c=1c=1(即询问),则输出当前第 nn 珍贵的宝石。

c=2c=2(即插入),则往系统中插入珍贵值为 nn 的宝石。

输出格式

对于每个 c=1c=1(询问),输出当前第 nn 珍贵的宝石的珍贵值 viv_i

5 3
1 3 2 5 6
1 3
2 4
1 6

3
1

提示

对于 50%50\% 的数据,没有 c=2c=2 的情况;

对于 100%100\% 的数据,m100000m\leq 100000c=2c=2 的情况不超过 1000010000 次,q30000q\leq 300001vi<2311 \leq v_i \lt 2^{31}