时间限制： 1.0 秒

空间限制： 512 MB

题目描述

你需要动态维护一个可重集合 $M$，并且提供以下操作：

1. 向 $M$ 中插入一个数 $x$。
2. 从 $M$ 中删除一个数 $x$，如果有多个 $x$ 同时在 $M$ 中，只删除其中一个。
3. 查询 $M$ 中有多少个数严格小于 $x$，将得到的答案 +1 再输出。
4. 查询将 $M$ 从小到大排列后，排为第 $x$ 位的数，排位从 1 开始计算。
5. 查询 $M$ 中严格小于 $x$ 的最大数。
6. 查询 $M$ 中严格大于 $x$ 的最小数。

我们保证：

• 对于操作 2，删除时 $M$ 中至少存在一个 $x$。
• 对于操作 3,5,6，不保证当前 $M$ 中存在数 $x$。
• 对于操作 5,6，保证答案一定存在。

输入格式

从标准输入读入数据。

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

接下来 $n$ 行，每行两个整数 $a,x$，$a$ 表示操作序号（$1\le a\le 6$），$x$ 表示对应的操作数。

输出格式

输出到标准输出。

输出若干行，对于操作 3,4,5,6，输出一行一个整数，表示对应答案。

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

106465
84185
492737

子任务

对于所有数据，保证 $1\le n\le 10^5,-10^7\le x\le 10^7$。

提示 0

本题作为搜索树的基础功能，可以用来测试邓俊辉《数据结构》上的各种搜索树（普通二叉搜索树、AVL 树、伸展树、B-树、红黑树）。虽然使用其他乱七八糟的方法也可以过，但是还是建议根据学习进度进行正常练习。

提示 1

本题当中前两种操作为搜索树的常规功能，后四种操作则可以基于搜索树的查找功能进行扩展，具体可以见 link。

提示 2

请注意本题维护的是可重集合，与邓俊辉《数据结构》中维护不可重集合的方式略有区别。还是可以参照上述链接进行退化情况的设计。

提示 3

本题数据强度较弱（同原始来源），因此普通二叉搜索树也可以过。如果你想对你实现的搜索树进行更强的数据测试，请前往以下评测链接：

• 洛谷 P3369，普通二叉搜索树可过测试点 13/14
• 洛谷 P6136，普通二叉搜索树可过测试点 14/24

来源

Tyvj 1728