#549. [TYVJ] 1728] 普通平衡树

[TYVJ] 1728] 普通平衡树

题目描述

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:

  1. 插入 xx

  2. 删除 xx 数(若有多个相同的数,因只删除一个)

  3. 查询 xx 数的排名(若有多个相同的数,因输出最小的排名)

  4. 查询排名为 xx 的数

  5. xx 的前驱(前驱定义为小于 xx ,且最大的数)

  6. xx 的后继(后继定义为大于 xx ,且最小的数)

输入格式

第一行为 nn ,表示操作的个数,下面 nn 行每行有两个数 optoptxxoptopt 表示操作的序号 (1opt6)(1 \le opt \le 6)

输出格式

对于操作 3,4,5,63,4,5,6 每行输出一个数,表示对应答案

样例

input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

output

106465
84185
492737

数据范围与提示

  1. nn 的数据范围:n100000n \le 100000

  2. 每个数的数据范围:[107,107][-10^7, 10^7]