【深基16.例7】普通二叉树（简化版）

题目描述

您需要写一种数据结构，来维护一些数（都是绝对值 $10^9$ 以内的数）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数 $q$ 不超过 $10^4$：

1. 定义数 $x$ 的排名为集合中小于 $x$ 的数的个数 $+1$。查询数 $x$ 的排名。注意 $x$ 不一定在集合里。
2. 查询排名为 $x(x\ge 1)$ 的数。保证集合里至少有 $x$ 个数。
3. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。若不存在则输出 $-2147483647$。
4. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。若不存在则输出 $2147483647$。
5. 插入一个数 $x$，本题的数据保证插入前 $x$ 不在集合中。

保证执行 $1,3,4$ 操作时，集合中有至少一个元素。

输入格式

第一行是一个整数 $q$，表示操作次数。

接下来 $q$ 行，每行两个整数 $op,x$，分别表示操作序号以及操作的参数 $x$。

输出格式

输出有若干行。对于操作 $1,2,3,4$，输出一个整数，表示该操作的结果。

输入样例 #1

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

输出样例 #1

2
3
1
5

输入样例 #2

31
5 345143628
5 -234930981
2 2
2 1
3 613037135
2 2
1 -69398046
2 1
5 300183398
4 33637881
2 2
1 930216782
5 -813510923
2 2
2 1
4 -889187821
1 132047758
3 923723813
1 113861096
4 -914888205
2 4
5 -585291132
3 380687570
2 3
3 548518308
2 2
1 754156584
5 -143767374
2 2
5 912731
3 646903190

输出样例 #2

345143628
-234930981
345143628
345143628
2
-234930981
300183398
300183398
4
-234930981
-813510923
-813510923
3
345143628
3
-813510923
345143628
345143628
-234930981
345143628
-585291132
6
-585291132
345143628

输入样例 #3

32
5 12854423
1 -52213545
5 383574996
2 1
3 -645096834
3 -137771734
5 421743297
4 998546861
4 -59784240
3 973240048
3 177011700
4 898203813
4 105693220
1 -176593618
5 716180925
1 -643206971
5 2322209
1 76102184
5 780436620
5 6005585
3 729107928
1 796769829
5 406345549
5 911855995
3 198029423
2 1
2 1
4 9809505
5 -968919202
5 712462655
2 1
2 3

输出样例 #3

1
12854423
-2147483647
-2147483647
2147483647
12854423
421743297
12854423
2147483647
383574996
1
1
3
716180925
8
12854423
2322209
2322209
12854423
-968919202
6005585

数据范围

其中需要提供以下操作，操作次数 $q$ 不超过 $10^4$

2. 查询排名为 $x(x\ge 1)$ 的数。

3. 插入一个数 $x$，本题的数据保证插入前 $x$ 不在集合中。

保证执行 $1,3,4$ 操作时，集合中有至少一个元素。