题目描述

这是一道模板题。

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

1. 插入 $x$ 数；
2. 删除 $x$ 数（若有多个相同的数，只删除一个）；
3. 查询 $x$ 数的排名（若有多个相同的数，输出最小的排名）；
4. 查询排名为 $x$ 的数；
5. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）；
6. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。

输入格式

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

下面 $n$ 行每行有两个数 $opt$ 和 $x$，$opt$ 表示操作的序号（$1 \le opt \le 6$）。

输出格式

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

样例

输入样例 1

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

输出样例 1

106465
84185
492737

样例解释

操作序列：

1. 1 106465：插入 106465。
2. 4 1：查询排名为 1 的数（最小数），当前只有 106465，输出 106465。
3. 1 317721：插入 317721。
4. 1 460929：插入 460929。
5. 1 644985：插入 644985。
6. 1 84185：插入 84185。
7. 1 89851：插入 89851。
8. 6 81968：查询 81968 的后继（大于 81968 的最小数）。当前集合排序：84185,89851,106465,317721,460929,644985。81968 的后继是 84185，输出 84185。
9. 1 492737：插入 492737。
10. 5 493598：查询 493598 的前驱（小于 493598 的最大数）。当前集合排序：84185,89851,106465,317721,460929,492737,644985。小于 493598 的最大数是 492737，输出 492737。

数据范围

• $1 \le n \le 10^5$
• $-10^7 \le x \le 10^7$

时间限制：1000 ms
内存限制：262144 KB

提示

本题为平衡树的模板题。可以使用多种平衡树实现，如：Treap（树堆）、Splay（伸展树）、AVL、红黑树等，也可以使用权值线段树或树状数组（需要离线离散化）。

常见实现方式：

1. Treap：每个节点有随机优先级，通过旋转维护堆性质，实现简单。
2. Splay：通过伸展操作将节点提到根，便于操作。
3. 无旋 Treap（FHQ Treap）：通过分裂合并实现，代码简洁。
4. 替罪羊树：通过重构维持平衡。

操作解释：

• 插入：按 BST 性质插入后调整平衡。
• 删除：找到节点，若为叶子直接删，否则用前驱或后继替换后删除。
• 查询排名：返回比 $x$ 小的数的个数 +1。
• 查询第 k 小：根据子树大小在 BST 中查找。
• 前驱：比 $x$ 小的最大数。
• 后继：比 $x$ 大的最小数。

注意：

• 可能有重复数字，处理重复时可以：
  • 每个节点维护一个计数 cnt 表示相同数字个数。
  • 或者允许 BST 中存在相同键值，但需要正确处理排名（多个相同数取最小排名）。
• 对于负数，平衡树应能正确处理比较。

推荐实现： FHQ Treap（无旋 Treap），代码较短且易于理解。