Vova 决定打扫他的房间。房间可以表示为坐标轴$$$OX$$$。房间里有$$$n$$$堆垃圾,第$$$i$$$堆的坐标是整数$$$p_i$$$。所有桩都有不同的坐标。
让我们将完全清理定义为以下过程。此过程的目标是收集不超过两个不同 $$$x$$$ 坐标中的所有桩。为了实现这一目标,Vova 可以执行多次(可能为零)动作。在一次移动过程中,他可以选择一些 $$$x$$$ 并使用扫帚将所有桩从 $$$x$$$ 移动到 $$$x+1$$$ 或 $$$x-1$$$。请注意,他无法选择要移动多少堆。
此外,还有两种类型的查询:
- $$$0$$$ $$$x$$$ — 从坐标 $$$x$$$ 移除一堆垃圾。保证此时坐标$$$x$$$处有一堆。
- $$$1$$$ $$$x$$$ — 将一堆垃圾添加到坐标$$$x$$$。保证此时坐标$$$x$$$处没有堆。
请注意,某个时刻房间内的垃圾堆可能为零。
Vova 想知道如果他想在任何查询之前进行彻底清理,他可以花费的最少移动次数。他还想知道应用每个查询后的移动次数。查询按给定顺序应用。请注意,完全清理实际上并没有发生,也不会改变桩的状态。它仅用于计算移动次数。
为了更好地理解,请阅读下面的注释部分以查看第一个示例的解释。
输入
输入的第一行包含两个整数 $$$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$$$ 中删除一堆,则 $$$1$$$ 是 $$$1$$$如果你需要在坐标$$$x_i$$$上添加一堆。保证对于 $$$t_i = 0$$$ 在当前的桩集中有这样的桩,而对于 $$$t_i = 1$$$ 在当前的桩集中不存在这样的桩。
输出
打印 $$$q+1$$$ 整数:Vova 在第一个查询之前和每个 $$$q$$$ 查询之后需要进行总清理的最小移动次数。
示例
输入 #1
5 6 1 2 6 8 10 1 4 1 9 0 6 0 10 1 100 1 50
输出 #1
5 7 7 5 4 8 49
输入 #2
5 8 5 1 2 4 3 0 1 0 2 0 3 0 4 0 5 1 1000000000 1 1 1 500000000
输出 #2
3 2 1 0 0 0 0 0 499999999
注意
考虑第一个例子。
最初,桩组是 $$$[1, 2, 6, 8, 10]$$$。第一个查询之前的答案是 $$$5$$$,因为您可以通过一次移动将所有桩从 $$$1$$$ 移动到 $$$2$$$,通过 $$$2$$$ 移动将所有桩从 $$$10$$$ 移动到 $$$8$$$,通过 $$$2$$$ 移动将所有桩从 $$$6$$$ 移动到 $$$8$$$。
第一次查询后,集合变为 $$$[1, 2, 4, 6, 8, 10]$$$。那么答案是 $$$7$$$ 因为您可以通过 $$$2$$$ 移动将所有桩从 $$$6$$$ 移动到 $$$4$$$,通过 $$$2$$$ 移动将所有桩从 $$$4$$$ 移动到 $$$2$$$,通过 $$$1$$$ 移动从 $$$2$$$ 到 $$$1$$$ 的所有桩以及从 $$$10$$$ 移动的所有桩$$$8$$$ 移动 $$$2$$$。
第二次查询后,桩组变为$$$[1, 2, 4, 6, 8, 9, 10]$$$,答案相同(并且之前的移动顺序可以应用于当前桩组)。
在第三次查询之后,这组桩变成 $$$[1, 2, 4, 8, 9, 10]$$$,答案是 $$$5$$$,因为你可以通过 $$$1$$$ 移动将所有桩从 $$$1$$$ 移动到 $$$2$$$,将所有桩从 $$$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$$$。