P5076 [Shenji 16. Example 7] Ordinary Binary Tree (Simplified Version).

You need to implement a data structure to maintain a set of numbers (all numbers have absolute value within $10^9$). The set is initially empty. You need to support the following operations, and the number of operations $q$ does not exceed $10^4$: 1. Define the rank of a number $x$ as the number of elements in the set that are less than $x$, plus $1$. Query the rank of $x$. **Note that $x$ may not be in the set**. 2. Query the number whose rank is $x$ ($x \ge 1$). **It is guaranteed that the set contains at least $x$ numbers**. 3. Find the predecessor of $x$ (the predecessor is defined as the largest number that is less than $x$). If it does not exist, output $-2147483647$. 4. Find the successor of $x$ (the successor is defined as the smallest number that is greater than $x$). If it does not exist, output $2147483647$. 5. Insert a number $x$. The testdata guarantees that before insertion, $x$ is not in the set. It is guaranteed that when performing operations $1$, $3$, and $4$, the set contains at least one element.

The first line contains an integer $q$, indicating the number of operations. In the next $q$ lines, each line contains two integers $op, x$, representing the operation index and the parameter $x$.

Output several lines. For operations $1$, $2$, $3$, and $4$, output one integer representing the result of the operation.

Translated by ChatGPT 5