← 返回题目列表

Codeforces · 1354/D

D. 多组

中文机器翻译题面 查看原题

请注意,内存限制不正常。

给你一个由 $$$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$$$ 不是唯一的答案。