Description

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.

Input Format

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 Format

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

7
5 1
5 3
5 5
1 3
2 2
3 3
4 3

2
3
1
5

Hint

Translated by ChatGPT 5