Description

Given a sequence that is initially empty, support the following three operations:

1. Given an integer $x$, insert $x$ into the sequence.
2. Output the smallest number in the sequence.
3. Delete the smallest number in the sequence (if multiple numbers are smallest, delete only $1$).

Input Format

The first line contains an integer $n$ representing the number of operations.
Then follow $n$ lines, each describing one operation. Each line first contains an integer $op$ indicating the operation type.

• If $op = 1$, then an integer $x$ follows, meaning to insert $x$ into the sequence.
• If $op = 2$, it means to output the smallest number in the sequence.
• If $op = 3$, it means to delete the smallest number in the sequence. If multiple numbers are smallest, delete only $1$.

Output Format

For each operation $2$, output one line with one integer representing the answer.

5
1 2
1 5
2
3
2

2
5

Hint

Constraints

• For $30\%$ of the testdata, it is guaranteed that $n \leq 15$.
• For $70\%$ of the testdata, it is guaranteed that $n \leq 10^4$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^6$, $1 \leq x \lt 2^{31}$, $op \in \{1, 2, 3\}$.

Translated by ChatGPT 5