8115076 - 【深基16.例7】普通二叉树(简化版)

通过次数

2

提交次数

10

时间限制 : 1 秒
内存限制 : 128 MB

您需要写一种数据结构,来维护一些数( 都是 10^9 以内的数字)的集合,最开始时集合是空的。其中需要提供以下操作,操作次数 q 不超过 10^4:

  1. 查询 x 数的排名(排名定义为比当前数小的数的个数 +1。若有多个相同的数,因输出最小的排名)。
  2. 查询排名为 x 的数。
  3. x 的前驱(前驱定义为小于 x,且最大的数)。若未找到则输出−2147483647。
  4. x 的后继(后继定义为大于 x,且最小的数)。若未找到则输出2147483647。
  5. 插入一个数 x

输入

输出

样例

输入

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

输出

2
3
1
5