← 返回题目列表

AtCoder · abc217_e

H. 排序查询

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

分数: 500 点

问题陈述

我们有一个空序列 A。你将被给予 Q 查询,应按照给出的顺序进行处理。 每个查询都是以下三种类型之一:

  • 1 x :追加 x 到年底 A.
  • 2 :打印开头的元素 A。然后,删除该元素。可以保证 给出此查询时, A 不会为空。
  • 3 :排序 A 按升序排列。

约束

  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq x \leq 10^9
  • A 查询时不会为空 给出了 2 。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

Q
\mathrm{query} 1
\mathrm{query} 2
\vdots
\mathrm{query} Q

的 i第一个查询, \mathrm{query} i,以查询类型开头 c_i (1, 2,或 3)。 如果 c_i = 1,该行另外还有一个整数 x.

换句话说,每个查询都采用以下三种格式之一。

1 x
2
3

输出

打印 q 行,其中 q 是查询的数量 c_i = 2.
的 j第行 (1 \leq j \leq q) 应包含以下内容的响应 j-第一个这样的查询。


示例输入 1

8
1 4
1 3
1 2
1 1
3
2
1 0
2

示例输出 1

1
2

的 i下面的第行显示了以下内容 A 之后 i- 第一个查询在示例输入中处理 1.

  • (4)
  • (4, 3)
  • (4, 3, 2)
  • (4, 3, 2, 1)
  • (1, 2, 3, 4)
  • (2, 3, 4)
  • (2, 3, 4, 0)
  • (3, 4, 0)

示例输入 2

9
1 5
1 5
1 3
2
3
2
1 6
3
2

示例输出 2

5
3
5

的 i下面的第行显示了以下内容 A 之后 i- 第一个查询在示例输入中处理 2.

  • (5)
  • (5, 5)
  • (5, 5, 3)
  • (5, 3)
  • (3, 5)
  • (5)
  • (5, 6)
  • (5, 6)
  • (6)