D. 序列
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个长度为 $$$n$$$ 的整数序列 $$$A = (a_1, a_2, \ldots, a_n)$$$。定义函数 $$$T(B)$$$ 如下：

对于任意长度为偶数的序列 $$$B$$$，Alice 和 Bob 轮流从中删除一个数（Alice 先手），直到剩下两个数。Alice 希望最后剩下的两个数的差的绝对值尽可能小，Bob 希望尽可能大。在双方均采取最优策略的前提下，记 $$$T(B)$$$ 为最终剩下的两个数的差的绝对值。

你需要维护序列 $$$A$$$，并按顺序处理以下两种操作：

  1. 修改：给定下标 $$$i$$$，将 $$$a_i$$$ 的值增加 $$$1$$$。
  2. 变换：给定整数 $$$t$$$，对序列 $$$A$$$ 中的所有元素执行变换： $$$$$$ a_i \leftarrow \begin{cases} a_i - t, & \text{if } a_i \gt t \\ t, & \text{if } a_i \le t \end{cases} $$$$$$

你需要按顺序处理这些操作，并在初始时以及每次操作后，输出当前序列 $$$A$$$ 对应的 $$$T(A)$$$ 的值。

Input

第一行输入两个整数 $$$n, q$$$ $$$(2 \le n \le 2 \times 10^5, 1 \le q \le 2 \times 10^5)$$$，分别表示序列长度和操作次数。保证 $$$n$$$ 为偶数。

第二行输入 $$$n$$$ 个整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^8)$$$，表示初始序列。

接下来 $$$q$$$ 行，每行描述一个操作：

  • 1 i：表示执行修改操作，将 $$$a_i$$$ 增加 $$$1$$$ $$$(1 \le i \le n)$$$。
  • 2 t：表示执行变换操作，对序列执行参数为 $$$t$$$ 的变换 $$$(1 \le t \le 10^8)$$$。
Output

输出共 $$$q + 1$$$ 行，每行一个整数。第 $$$1$$$ 行表示初始序列的 $$$T(A)$$$ 值。

接下来第 $$$2$$$ 到第 $$$q + 1$$$ 行依次表示每次操作后的 $$$T(A)$$$ 值。

Example
Input
6 3
1 3 6 5 4 9
1 3
2 3
1 4
Output
3
4
2
1