题目描述

瓦尼亚发明了一个有趣的整数集合魔术。

假设魔术师有一个正整数集合 $S$。他会说出一个正整数 $x$。观众需要选择一个 $S$ 的子集（可以是空集），但不能让魔术师看到。接着，观众告诉魔术师所选子集的大小。魔术的重点在于，魔术师随后需要猜出：所选子集的元素之和是否不超过 $x$。对于空集，假设其和为 $0$。

瓦尼亚非常喜欢这个魔术，因此开始准备向公众展示。为此，他准备了一个由不同正整数组成的集合 $S$。当然，瓦尼亚希望魔术一定能成功。他将一个正整数 $x$ 定义为失败的，如果他无法确定对于观众选择的任何子集，魔术都能成功。

为了评估他选择的集合 $S$ 的好坏，他想计算出对于该集合有多少个失败的正整数。

此外，瓦尼亚计划测试不同的集合 $S$。因此，他请求你编写一个程序，计算初始集合 $S$ 的失败正整数数量，以及每次修改后的集合 $S$ 的失败正整数数量。瓦尼亚将进行 $q$ 次集合修改，每次修改为以下两种操作之一：

• 在集合 $S$ 中添加一个新数字 $a$。
• 从集合 $S$ 中删除一个数字 $a$。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \leq n, q \leq 200000)$，分别表示初始集合 $S$ 的大小和修改次数。

第二行包含 $n$ 个不同的整数 $s_1, s_2, \ldots, s_n$ $(1 \leq s_i \leq 10^{13})$，表示初始集合 $S$ 的元素。

接下来的 $q$ 行，每行包含两个整数 $t_i$ 和 $a_i$ $(1 \leq t_i \leq 2, 1 \leq a_i \leq 10^{13})$，描述一次修改操作。

• 如果 $t_i = 1$，则表示将新数字 $a_i$ 添加到集合 $S$ 中。保证在执行操作前，该数字不在集合 $S$ 中。
• 如果 $t_i = 2$，则表示从集合 $S$ 中删除数字 $a_i$。保证在执行操作前，该数字在集合 $S$ 中。

输出格式

输出 $q + 1$ 行。

第一行输出初始集合 $S$ 的失败正整数数量。接下来的 $q$ 行输出每次修改后集合 $S$ 的失败正整数数量。

3 11
1 2 3
2 1
1 5
1 6
1 7
2 6
2 2
2 3
1 10
2 5
2 7
2 10

4
1
6
12
19
13
8
2
10
3
0
0

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。