E - Sorting Queries Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

空の列 A があります。クエリが Q 個与えられるので、与えられた順番に処理してください。
クエリは次の 3 種類のいずれかです。

  • 1 x : A の最後尾に x を追加する。
  • 2 : A の最初の要素を出力する。その後、その要素を削除する。このクエリが与えられるとき、A は空でないことが保証される。
  • 3 : A を昇順にソートする。

制約

  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq x \leq 10^9
  • クエリ 2 が与えられるとき、A は空でない。
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

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

i 番目のクエリ \mathrm{query} i では、まずクエリの種類 c_i（ 1, 2, 3 のいずれか）が与えられる。 c_i = 1 の場合はさらに整数 x が追加で与えられる。

すなわち、各クエリは以下に示す 3 つの形式のいずれかである。

1 x

2

3

出力

c_i = 2 を満たすクエリの回数を q として 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 の状態を i 行目に示すと以下のようになります。

  • (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 の状態を i 行目に示すと以下のようになります。

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

Score : 500 points

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)