[SDOI2007]超级数组

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 arr.in 输出文件 arr.out

Source: SDOI2007 Day2
【问题描述】

一般的数组大家都经常使用，相信很多同学没有见过下面的超级数组。
超级数组存储的是一些正整数，它还支持下面的两个操作
(1)、插入一个元素，命令是 "i key" 。 key 是要插入的数。
(2)、输出第 k 大元素并删除该元素，命令是 "d k"。输出第 k 大元素并删除它。
“第 k 大”是指：现有的数中，如果从小到大排好序，从最小的开始作为第一大算起，
一直数到第 k 个。
现在给出一个开始是空的超级数组，请维护好该数组。
【输入】(arr.in)
第一行 n、m：n<=1 000 000 000 , m<=100 000。表示插入数的范围是 1 至n ,共有m 条
命令（包括插入和删除）。
以下 m 行，每行一条命令，如题中描述。每条命令中字母和后面的数字之间一个空格。
保证输入数据是正确的，删除的数一定存在。
【输出】（arr.out）
对于每个删除命令，按删除命令顺序输出删除的数，每个数一行
【样例输入】
100 10
i 57
i 99
i 65
d 3
i 89
d 2
d 2
d 1
i 93
i 29
【样例输出】
99
65
89
57