该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

二叉查找树是一种维护有序序列的数据结构，形态上是二叉树。支持查询前驱，后继，第 $k$ 大，$x$ 的排名等操作。

维护一个 $\text{BST}$（二叉查找树），初始序列为空，支持以下 $5$ 种操作。

    $1.$ 查询 $x$ 的排名（排名：比 $x$ 小的数的个数$+1$）。

    $2.$ 查询排名为 $k$ 的数。

    $3.$ 查询 $x$ 的前驱（比 $x$ 小的最大值）。

    $4.$ 查询 $x$ 的后继（比 $x$ 大的最小值）。

    $5.$ 插入 $x$。

Input Format

第一行一个整数 $n$ 表示操作次数。

接下来 $n$ 行，每行表示一个操作，可能是以下 $5$ 种：

    $1.$ 1 x 查询 x 的排名，

    $2.$ 2 k 查询排名为 $k$ 的数。

    $3.$ 3 x 查询 $x$ 的前驱。

    $4.$ 4 x 查询 $x$ 的后继。

    $5.$ 5 x 插入 $x$。

Output Format

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

2
3
1
5

Hint

Source