Description

You need to dynamically maintain a multiset $M$ and support the following operations:

1. Insert a number $x$ into $M$.
2. Delete a number $x$ from $M$ (if there are multiple equal numbers, delete only one).
3. Query how many numbers in $M$ are less than $x$, and then add one to the result (i.e., the rank of $x$).
4. Query the number whose rank is $x$ when $M$ is sorted in ascending order.
5. Query the predecessor of $x$ in $M$ (the predecessor is defined as the maximum number that is less than $x$).
6. Query the successor of $x$ in $M$ (the successor is defined as the minimum number that is greater than $x$).

For operations 3, 5, and 6, it is not guaranteed that $x$ exists in the current multiset.

For operations 5 and 6, the answer is guaranteed to exist.

Input Format

The first line contains $n$, the number of operations. Each of the next $n$ lines contains two integers $\text{opt}$ and $x$, where $\text{opt}$ denotes the operation index ($1 \leq \text{opt} \leq 6$).

Output Format

For operations 3, 4, 5, and 6, output one integer per line, the corresponding answer.

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

106465
84185
492737

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 10^5$, $|x| \le 10^7$.

Source: Tyvj1728, originally titled: Ordinary Balanced Tree.

Special thanks!

Translated by ChatGPT 5