Score : $500$ points

问题描述

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

• 1 x：将 $x$ 添加到 $A$ 的末尾。
• 2：打印 $A$ 开头的元素。然后，删除该元素。保证在给出此查询时，$A$ 不会为空。
• 3：将 $A$ 按升序排列。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have an empty sequence $A$. You will be given $Q$ queries, which should be processed in the order they are given. Each query is of one of the three kinds below:

• 1 x : Append $x$ to the end of $A$.
• 2 : Print the element at the beginning of $A$. Then, delete that element. It is guaranteed that $A$ will not empty when this query is given.
• 3 : Sort $A$ in ascending order.

Constraints

• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq x \leq 10^9$
• $A$ will not be empty when a query 2 is given.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$Q$

$\mathrm{query} 1$

$\mathrm{query} 2$

$\vdots$

$\mathrm{query} Q$

The $i$-th query, $\mathrm{query} i$, begins with the kind of query $c_i$ ($1$, $2$, or $3$). If $c_i = 1$, the line additionally has an integer $x$.

In other words, each query is in one of the three formats below.

$1$ $x$

$2$

$3$

Output

Print $q$ lines, where $q$ is the number of queries with $c_i = 2$.
The $j$-th line $(1 \leq j \leq q)$ should contain the response for the $j$-th such query.

Sample Input 1

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

Sample Output 1

1
2

The $i$-th line below shows the contents of $A$ after the $i$-th query is processed in Sample Input $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)$

Sample Input 2

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

Sample Output 2

5
3
5

The $i$-th line below shows the contents of $A$ after the $i$-th query is processed in Sample Input $2$.

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

update @ 2024/3/10 09:37:05