P3369 【Template】Ordinary Balanced Tree

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.

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$).

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

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