CF1500E.Subset Trick

Vanya invented an interesting trick with a set of integers.

Let an illusionist have a set of positive integers $S$. He names a positive integer $x$. Then an audience volunteer must choose some subset (possibly, empty) of $S$ without disclosing it to the illusionist. The volunteer tells the illusionist the size of the chosen subset. And here comes the trick: the illusionist guesses whether the sum of the subset elements does not exceed $x$. The sum of elements of an empty subset is considered to be $0$.

Vanya wants to prepare the trick for a public performance. He prepared some set of distinct positive integers $S$. Vasya wants the trick to be successful. He calls a positive number $x$ unsuitable, if he can't be sure that the trick would be successful for every subset a viewer can choose.

Vanya wants to count the number of unsuitable integers for the chosen set $S$.

Vanya plans to try different sets $S$. He wants you to write a program that finds the number of unsuitable integers for the initial set $S$, and after each change to the set $S$. Vanya will make $q$ changes to the set, and each change is one of the following two types:

• add a new integer $a$ to the set $S$, or
• remove some integer $a$ from the set $S$.

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

假设一位魔术师拥有一个正整数集合 $S$。他宣布一个正整数 $x$。接着，一名观众志愿者需在不向魔术师透露的前提下，从 $S$ 中任选一个子集（可以为空）。志愿者仅告诉魔术师所选子集的大小（即元素个数）。此时魔术的关键环节来了：魔术师需判断该子集所有元素之和是否不超过 $x$。空子集的元素和定义为 $0$。

万尼亚打算为一场公开演出准备这个魔术。他已预先准备了一个由互异正整数构成的集合 $S$。瓦夏希望该魔术总能成功。他将一个正整数 $x$ 称为不合适的，当且仅当他无法保证：对观众可能选择的任意子集，该魔术均能成功。

万尼亚希望统计出对于给定集合 $S$，有多少个正整数是不合适的。

万尼亚计划尝试不同的集合 $S$。他要求你编写一个程序：首先计算初始集合 $S$ 对应的不合适整数的个数；随后，在每次对集合 $S$ 进行修改后，再次计算该个数。万尼亚总共会执行 $q$ 次修改操作，每次操作为以下两种类型之一：

• 向集合 $S$ 中添加一个新整数 $a$，或
• 从集合 $S$ 中删除某个整数 $a$。

The first line contains two integers $n$, $q$ ($1 \leq n, q \leq 200\,000$) — the size of the initial set $S$ and the number of changes.

The next line contains $n$ distinct integers $s_1, s_2, \ldots, s_n$ ($1 \leq s_i \leq 10^{13}$) — the initial elements of $S$.

Each of the following $q$ lines contain two integers $t_i$, $a_i$ ($1 \leq t_i \leq 2$, $1 \leq a_i \leq 10^{13}$), describing a change:

• If $t_i = 1$, then an integer $a_i$ is added to the set $S$. It is guaranteed that this integer is not present in $S$ before this operation.
• If $t_i = 2$, then an integer $a_i$ is removed from the set $S$. In is guaranteed that this integer is present in $S$ before this operation.

第一行包含两个整数 $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$，则将整数 $a_i$ 从集合 $S$ 中移除。保证该整数在本次操作前存在于 $S$ 中。

Print $q + 1$ lines.

In the first line print the number of unsuitable integers for the initial set $S$. In the next $q$ lines print the number of unsuitable integers for $S$ after each change.

输出 $q + 1$ 行。

第一行输出初始集合 $S$ 中不合适的整数的个数。接下来的 $q$ 行，每行输出每次修改后集合 $S$ 中不合适的整数的个数。

In the first example the initial set is $S = {1, 2, 3}$. For this set the trick can be unsuccessful for $x \in {1, 2, 3, 4}$. For example, if $x = 4$, the volunteer can choose the subset ${1, 2}$ with sum $3 \leq x$, and can choose the subset ${2, 3}$ with sum $5 \gt x$. However, in both cases the illusionist only know the same size of the subset ($2$), so he can't be sure answering making a guess. Since there is only one subset of size $3$, and the sum of each subset of smaller size does not exceed $5$, all $x \ge 5$ are suitable.

在第一个例子中，初始集合为 $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$ 均为可行的取值。