Problem9858--二叉搜索树 —— 3. 二叉排序树

9858: 二叉搜索树 —— 3. 二叉排序树

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

你需要写一种数据结构,来维护一些数,其中需要提供以下操作:

  1. 插入数值 x。
  2. 删除数值 x。
  3. 输出数值 x 的前驱,前驱定义为现有所有数中小于 x 的最大的数。
  4. 输出数值 x 的后继,后继定义为现有所有数中大于 x 的最小的数。

题目保证:

  • 操作 1 插入的数值各不相同。
  • 操作 2 删除的数值一定存在。
  • 操作 3 和 4 的结果一定存在。

Input

第一行包含整数 n,表示共有 n 个操作命令。

接下来 n 行,每行包含两个整数 opt 和 x,表示操作序号和操作数值。

Output

对于操作 3,4,每行输出一个操作结果。

Constraints

$1≤n≤2,000$
$−10000≤x≤10000$

Sample 1 Input

6
1 1
1 3
1 5
3 4
2 3
4 2

Sample 1 Output

3
5

Source/Category

二叉搜索树 BST