题目描述

我们有一个空序列 $A$。你将会收到 $Q$ 个查询，并按照给定的顺序进行处理。每个查询属于以下三种类型之一：

• 1 x：在序列的末尾追加 $x$。
• 2：打印序列开头的元素，然后删除该元素。当执行此查询时，保证 $A$ 不为空。
• 3：按照升序对 $A$ 进行排序。

约束条件

• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq x \leq 10^9$
• 当执行查询 2 时，保证 $A$ 不为空。
• 输入的所有值都是整数。

输入格式

从标准输入读入数据，输入格式如下：

$Q$
$query_1$
$query_2$
$\vdots$
$query_Q$

第 $i$ 个查询 $query_i$ 的开始表示查询的类型 $c_i$（$1$、$2$ 或 $3$）。如果 $c_i = 1$，则该行额外包含一个整数 $x$。

换句话说，每个查询属于以下三种格式之一：

$1$ $x$
$2$
$3$

输出格式

按照查询中 $c_i = 2$ 的数量，打印 $q$ 行。
第 $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

在示例输入1中，第 $i$ 个查询后的序列 $A$ 的内容如下所示：

• $(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

在示例输入2中，第 $i$ 个查询后的序列 $A$ 的内容如下所示：

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