CF1418D.Trash Problem

Vova decided to clean his room. The room can be represented as the coordinate axis $OX$. There are $n$ piles of trash in the room, coordinate of the $i$-th pile is the integer $p_i$. All piles have different coordinates.

Let's define a total cleanup as the following process. The goal of this process is to collect all the piles in no more than two different $x$ coordinates. To achieve this goal, Vova can do several (possibly, zero) moves. During one move, he can choose some $x$ and move all piles from $x$ to $x+1$ or $x-1$ using his broom. Note that he can't choose how many piles he will move.

Also, there are two types of queries:

• $0$ $x$ — remove a pile of trash from the coordinate $x$. It is guaranteed that there is a pile in the coordinate $x$ at this moment.
• $1$ $x$ — add a pile of trash to the coordinate $x$. It is guaranteed that there is no pile in the coordinate $x$ at this moment.

Note that it is possible that there are zero piles of trash in the room at some moment.

Vova wants to know the minimum number of moves he can spend if he wants to do a total cleanup before any queries. He also wants to know this number of moves after applying each query. Queries are applied in the given order. Note that the total cleanup doesn't actually happen and doesn't change the state of piles. It is only used to calculate the number of moves.

For better understanding, please read the Notes section below to see an explanation for the first example.

沃瓦决定打扫他的房间。房间可以表示为坐标轴 $OX$。房间里有 $n$ 堆垃圾，第 $i$ 堆垃圾的坐标为整数 $p_i$。所有垃圾堆的坐标互不相同。

我们定义一次“全面清理”为如下过程：该过程的目标是将所有垃圾堆收集到至多两个不同的 $x$ 坐标上。为达成此目标，沃瓦可以执行若干次（可能为零次）移动操作。每次操作中，他可以选择某个坐标 $x$，并用扫帚将位于 $x$ 处的所有垃圾堆整体移动到 $x+1$ 或 $x-1$。注意：他不能选择仅移动其中一部分垃圾堆。

此外，存在两种类型的查询：

• $0$ $x$ —— 从坐标 $x$ 处移除一堆垃圾。保证此时坐标 $x$ 上确实存在一堆垃圾。
• $1$ $x$ —— 在坐标 $x$ 处添加一堆垃圾。保证此时坐标 $x$ 上尚无垃圾堆。

注意：在某些时刻，房间中可能没有垃圾堆。

沃瓦希望知道：在任意查询执行前，若要进行一次全面清理，他最少需要花费多少次移动操作；他还希望知道在每次查询执行后，该最小移动次数是多少。查询按给定顺序依次应用。注意：“全面清理”本身并不会真实发生，也不会改变垃圾堆的状态；它仅用于计算所需的最少移动次数。

为便于理解，请参阅下方“说明”部分，其中对第一个样例进行了详细解释。

The first line of the input contains two integers $n$ and $q$ ($1 \le n, q \le 10^5$) — the number of piles in the room before all queries and the number of queries, respectively.

The second line of the input contains $n$ distinct integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 10^9$), where $p_i$ is the coordinate of the $i$-th pile.

The next $q$ lines describe queries. The $i$-th query is described with two integers $t_i$ and $x_i$ ($0 \le t_i \le 1; 1 \le x_i \le 10^9$), where $t_i$ is $0$ if you need to remove a pile from the coordinate $x_i$ and is $1$ if you need to add a pile to the coordinate $x_i$. It is guaranteed that for $t_i = 0$ there is such pile in the current set of piles and for $t_i = 1$ there is no such pile in the current set of piles.

输入的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^5$）——分别表示初始时房间中石堆的数量以及查询的总数。

输入的第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le 10^9$），其中 $p_i$ 表示第 $i$ 个石堆的坐标。

接下来的 $q$ 行描述了各次查询。第 $i$ 次查询由两个整数 $t_i$ 和 $x_i$（$0 \le t_i \le 1$；$1 \le x_i \le 10^9$）给出：若 $t_i = 0$，表示需从坐标 $x_i$ 处移除一个石堆；若 $t_i = 1$，表示需在坐标 $x_i$ 处添加一个石堆。保证对于所有满足 $t_i = 0$ 的查询，当前石堆集合中确实存在坐标为 $x_i$ 的石堆；而对于所有满足 $t_i = 1$ 的查询，当前石堆集合中不存在坐标为 $x_i$ 的石堆。

Print $q+1$ integers: the minimum number of moves Vova needs to do a total cleanup before the first query and after each of $q$ queries.

输出 $q+1$ 个整数：Vova 在第一个查询之前以及每次 $q$ 个查询之后完成一次彻底清理所需的最少移动次数。

Consider the first example.

Initially, the set of piles is $[1, 2, 6, 8, 10]$. The answer before the first query is $5$ because you can move all piles from $1$ to $2$ with one move, all piles from $10$ to $8$ with $2$ moves and all piles from $6$ to $8$ with $2$ moves.

After the first query, the set becomes $[1, 2, 4, 6, 8, 10]$. Then the answer is $7$ because you can move all piles from $6$ to $4$ with $2$ moves, all piles from $4$ to $2$ with $2$ moves, all piles from $2$ to $1$ with $1$ move and all piles from $10$ to $8$ with $2$ moves.

After the second query, the set of piles becomes $[1, 2, 4, 6, 8, 9, 10]$ and the answer is the same (and the previous sequence of moves can be applied to the current set of piles).

After the third query, the set of piles becomes $[1, 2, 4, 8, 9, 10]$ and the answer is $5$ because you can move all piles from $1$ to $2$ with $1$ move, all piles from $2$ to $4$ with $2$ moves, all piles from $10$ to $9$ with $1$ move and all piles from $9$ to $8$ with $1$ move.

After the fourth query, the set becomes $[1, 2, 4, 8, 9]$ and the answer is almost the same (the previous sequence of moves can be applied without moving piles from $10$).

After the fifth query, the set becomes $[1, 2, 4, 8, 9, 100]$. You can move all piles from $1$ and further to $9$ and keep $100$ at its place. So the answer is $8$.

After the sixth query, the set becomes $[1, 2, 4, 8, 9, 50, 100]$. The answer is $49$ and can be obtained with almost the same sequence of moves as after the previous query. The only difference is that you need to move all piles from $50$ to $9$ too.

考虑第一个例子。

初始时，石堆集合为 $[1, 2, 6, 8, 10]$。第一次查询前的答案为 $5$，因为你可以：将所有位于 $1$ 的石堆移动到 $2$（耗时 $1$ 步），将所有位于 $10$ 的石堆移动到 $8$（耗时 $2$ 步），以及将所有位于 $6$ 的石堆移动到 $8$（耗时 $2$ 步）。

第一次查询后，石堆集合变为 $[1, 2, 4, 6, 8, 10]$。此时答案为 $7$，因为你可以：将所有位于 $6$ 的石堆移动到 $4$（耗时 $2$ 步），将所有位于 $4$ 的石堆移动到 $2$（耗时 $2$ 步），将所有位于 $2$ 的石堆移动到 $1$（耗时 $1$ 步），以及将所有位于 $10$ 的石堆移动到 $8$（耗时 $2$ 步）。

第二次查询后，石堆集合变为 $[1, 2, 4, 6, 8, 9, 10]$，答案保持不变（前述移动序列仍适用于当前石堆集合）。

第三次查询后，石堆集合变为 $[1, 2, 4, 8, 9, 10]$，答案为 $5$，因为你可以：将所有位于 $1$ 的石堆移动到 $2$（耗时 $1$ 步），将所有位于 $2$ 的石堆移动到 $4$（耗时 $2$ 步），将所有位于 $10$ 的石堆移动到 $9$（耗时 $1$ 步），以及将所有位于 $9$ 的石堆移动到 $8$（耗时 $1$ 步）。

第四次查询后，石堆集合变为 $[1, 2, 4, 8, 9]$，答案几乎相同（前述移动序列仍适用，只是无需再移动原本位于 $10$ 的石堆）。

第五次查询后，石堆集合变为 $[1, 2, 4, 8, 9, 100]$。你可以将所有从 $1$ 开始的石堆全部移动至 $9$，同时保持 $100$ 原地不动。因此答案为 $8$。

第六次查询后，石堆集合变为 $[1, 2, 4, 8, 9, 50, 100]$。答案为 $49$，其移动方案与上一次查询后几乎相同，唯一区别在于：还需将所有位于 $50$ 的石堆也移动至 $9$。