← 返回题目列表

AtCoder · arc033_3

C. 数据结构

中文机器翻译题面 查看原题

問題文

一组数字 处理 S 的以下查询。

  • 类型 1 : S 转至号码 添加 X 。
  • 类型 2 : S 中包含的数字 回答 X 第一个最小的数字并 从 S 中删除。

入力

输入是按以下格式从标准输入给出的。

Q
T_1 X_1
T_2 X_2
:
T_Q X_Q
  • 1 行包含一个表示查询数量的整数。 来自行 Q (1 ≦ Q ≦ 200,000) 。 来自行
  • 2 从线 Q 行提供有关查询的信息。其中 在行 i 中,2 整数 T_i (1 ≦ T_i ≦ 2), X_i (1 ≦ X_i ≦ 200,000) 用空格分隔。这是 对于
    • T_i = 1 ,“ 表示查询“AddS 转至号码 添加 X_i ”。但是,在处理查询之前 S 有 X_i 保证不包含在内。 表示查询“从
    • T_i = 2 ,“ 表示查询“AddS 中包含的数字 回答 X_i 第一个最小的数字并 从 S 中删除”。但是,在处理查询之前 S 中包含的数字个数为 保证至少为 X_i 。

出力

类型 2 的查询数量 Q_2 那么输出是 由 Q_2 行组成。其中 i 类型 2 的查询 打印第 i 个答案。还在输出末尾添加换行符。


入力例1

5
1 11
1 29
1 89
2 2
2 2

出力例1

29
89

入力例2

12
1 8932
1 183450
1 34323
1 81486
1 127874
1 114850
1 55277
1 112706
2 3
1 39456
1 52403
2 4

出力例2

55277
52403