请注意,内存限制不正常。
给你一个由 $$$n$$$ 整数组成的多重集。您必须处理两种类型的查询:
- 将整数 $$$k$$$ 添加到多重集中;
- 找到多重集中的第 $$$k$$$ 阶统计数据并将其删除。
多重集中的第 $$$k$$$ 顺序统计信息是多重集中所有元素的排序列表中的第 $$$k$$$ 个元素。例如,如果多重集包含元素 $$$1$$$、$$$4$$$、$$$2$$$、$$$1$$$、$$$4$$$、$$$5$$$、$$$7$$$ 和 $$$k = 3$$$,则必须在 $$$[1, 1, 2, 4, 4, 5, 7]$$$,即$$$2$$$。如果您尝试删除在多重集中多次出现的元素,则只会删除一次出现的元素。
处理完所有查询后,打印属于多重集的任何数字,或者说它是空的。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 10^6$$$) — 分别是初始多重集中的元素数量和查询数量。
第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le n$$$) — 多重集的元素。
第三行包含 $$$q$$$ 整数 $$$k_1$$$, $$$k_2$$$, ..., $$$k_q$$$,每个表示一个查询:
- 如果 $$$1 \le k_i \le n$$$,则第 $$$i$$$ 查询为“将 $$$k_i$$$ 插入多重集中”;
- 如果 $$$k_i < 0$$$,则第 $$$i$$$ 查询是“从多重集中删除第 $$$|k_i|$$$ 个订单统计信息”。对于此查询,保证 $$$|k_i|$$$ 不大于多重集的大小。
输出
如果在所有查询后多重集为空,则打印 $$$0$$$。
否则,打印属于结果多重集的任何整数。
示例
输入 #1
5 5 1 2 3 4 5 -1 -1 -1 -1 -1
输出 #1
0
输入 #2
5 4 1 2 3 4 5 -5 -1 -3 -1
输出 #2
3
输入 #3
6 2 1 1 1 2 3 4 5 6
输出 #3
6
注意
在第一个示例中,多重集的所有元素都被删除。
在第二个示例中,元素 $$$5$$$、$$$1$$$、$$$4$$$、$$$2$$$ 被删除(它们按删除的时间顺序列出)。
在第三个示例中,$$$6$$$ 不是唯一的答案。