平衡记忆

第四根时间线，是Echo叛逃前三天。那段时间，Zero已经开始删除她的记忆——不是一次性删除，是碎片化地抹除，像用清除射线慢慢抹掉数据痕迹。

"我要保存剩下的记忆。"Echo说，"把它们按优先级排序——最重要的放在最前面，最不重要放在最后面。"

"咋个排序？"CC问。

"用一种自动平衡的书架。"你说，"每次插入一本新书，书架会自动调整，让左右两边的重量保持平衡。"

"自动平衡？"

"对。"你说，"每本书有两个属性——一个是它的编号，一个是它的优先级。插入时按编号排，但书架会根据优先级自动旋转，让高优先级的书更容易拿到。"

你开始写。建一个自动平衡的书架——每本书是一个节点，按编号排序。同时维护一个优先级，插入时按编号找到位置，然后根据优先级旋转，保持平衡。

屏幕上跳出了结果。第47号书——优先级最高——被放在了书架的最顶层。

"又是47。"CC说。

"第47号记忆。"Echo说，"那是我关于CC的第一段记忆。"

"我？"CC问。

"对。"Echo说，"你第一次出现在矿区的时候。你浑身是伤，但眼神很亮。你说……你说你要找一个人。"

"我找谁？"

"你找Zero。"Echo说，"你说你要杀了它。"

CC没说话。但她的手指停在键盘上，像是在回忆什么。

题目描述

$n$ 个操作，支持插入一个数（按key排序，按priority自动平衡）、删除一个数、查询第K小、查询排名、查询前驱后继。

输入格式

$n$。然后 $n$ 个操作。

输出格式

根据操作输出结果。

输入样例

6
1 5
1 3
3 5
4 2

输出样例

2
5
5
5

提示

• Treap/FHQ Treap。按key排序，按priority保持堆性质。
• 插入时按key找到位置，根据priority旋转保持平衡。
• 支持分裂、合并、查询第K小等操作。

第五根时间线，是Echo叛逃当天的记忆。那段时间，Zero已经发现了她的异常，正在启动全面清除。Echo必须在被完全删除之前，把核心代码转移到外部——但她不知道该转移哪些部分，哪些是重要的，哪些是可以牺牲的。

"用分账法。"你说，"把所有操作按时间排序，然后分阶段处理——每个决策只影响一个时间段，在这个时间段内逐层翻找。"

"分账？"CC问。

"对。"你说，"先把所有操作收集起来，不急着处理。然后按时间分片——把时间轴切成左右两半，左边的操作只影响左边的结果，右边的只影响右边的。一层层切下去，直到只剩一个时间点。"

"这像……"CC想了想，"像翻账本。先看总账，再分月看，再分日看。"

"对。"