宝石管理系统

题目描述

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

输入输出格式

输入格式


第一行一个整数m,q,表示已经取出来的宝石个数以及接下来的查询或插入操作个数。 第二行m个整数,表示这m个宝石的珍贵值。 以下q行,每行两个整数c,n, 若c=1(即询问),则输出当前第n珍贵的宝石, 若c=2(即插入),则往系统中插入珍贵值为n的宝石。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

3
1

说明

对于50%的数据,没有c=2的情况; 对于100%的数据,m<=100000,c=2的情况不超过10000,q<=30000