Vanya 用一组整数发明了一个有趣的技巧。
让一个魔术师有一组正整数$$$S$$$。他命名了一个正整数$$$x$$$。然后,观众志愿者必须选择 $$$S$$$ 的某个子集(可能是空的),而不将其透露给魔术师。志愿者告诉魔术师所选子集的大小。技巧来了:魔术师猜测子集元素的总和是否不超过$$$x$$$。空子集的元素总和被认为是$$$0$$$。
Vanya 想要为公开表演准备这个戏法。他准备了一组不同的正整数$$$S$$$。瓦夏希望诡计成功。如果他不能确定该技巧对于观看者可以选择的每个子集都会成功,那么他认为正数 $$$x$$$ 是不合适的。
Vanya 想要计算所选集合 $$$S$$$ 中不合适的整数的数量。
Vanya 计划尝试不同的组合 $$$S$$$。他希望你编写一个程序,找出初始集合 $$$S$$$ 以及每次更改集合 $$$S$$$ 后不合适的整数的数量。 Vanya 将对集合进行 $$$q$$$ 更改,每次更改都是以下两种类型之一:
- 将新整数 $$$a$$$ 添加到集合 $$$S$$$ 中,或者
- 从集合 $$$S$$$ 中删除一些整数 $$$a$$$。
输入
第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1 \leq n, q \leq 200\,000$$$) — 初始集合 $$$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$$$ 不合适的整数的数量。
示例
输入 #1
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
输出 #1
4 1 6 12 19 13 8 2 10 3 0 0
注意
在第一个示例中,初始集是 $$$S = \{1, 2, 3\}$$$。对于这个集合,对于 $$$x \in \{1, 2, 3, 4\}$$$ 来说,这个技巧可能不成功。例如,如果$$$x = 4$$$,则志愿者可以选择子集$$$\{1, 2\}$$$,总和为$$$3 \leq x$$$,并且可以选择子集$$$\{2, 3\}$$$,总和为$$$5 > x$$$。然而,在这两种情况下,魔术师只知道子集的相同大小($$$2$$$),所以他不能确定回答猜测。由于只有一个大小为 $$$3$$$ 的子集,并且每个较小大小的子集之和不超过 $$$5$$$,因此所有 $$$x \ge 5$$$ 都是合适的。