Alice 拥有一堆木棍。最初，对于每个 $\ell = 1, \dots, N$，她有 $c_\ell$ 根长度为 $\ell$ 的木棍。
Alice 想要用她的木棍制作一些等腰三角形。一个等腰三角形由两根长度相同的木棍（设为 $\ell$）和第三根长度在 $1$ 到 $2\ell - 1$ 之间的木棍组成。注意，三角形必须严格满足三角形不等式，等边三角形也是允许的。每根木棍最多只能用于一个三角形。Alice 想知道她用这些木棍最多能制作多少个等腰三角形。
有 $Q$ 个事件会改变她拥有的木棍集合。第 $i$ 个事件包含两个整数 $\ell_i$ 和 $d_i$，表示长度为 $\ell_i$ 的木棍数量变化了 $d_i$。注意 $d_i$ 可以是正数、负数或 $0$，但 Alice 拥有的每种长度的木棍数量永远不会为负数，也不会超过 $10^9$。
你的任务是确定在每次事件之后，如果 Alice 采取最优策略，她最多能制作多少个等腰三角形。
输入格式
第一行包含两个空格分隔的整数 $N$ 和 $Q$。
第二行包含 $N$ 个空格分隔的整数 $c_1, c_2, \dots, c_N$ ($0 \le c_i \le 10^9$)，表示 Alice 最初的木棍集合。
接下来的 $Q$ 行，每行包含两个空格分隔的整数 $\ell_i$ 和 $d_i$ ($1 \le \ell_i \le N, -10^9 \le d_i \le 10^9$)，表示一个事件。
最初以及每次事件之后，对于所有 $\ell = 1, \dots, N$，长度为 $\ell$ 的木棍数量都在 $0$ 到 $10^9$ 之间。
子任务
| 分值 | $N, Q$ 的范围 | 附加约束 | ||
|---|---|---|---|---|
| 5 分 | $1 \le N, Q \le 2\,000$ | 最初及每次事件后总木棍数不超过 $2\,000$ | ||
| 5 分 | $1 \le N, Q \le 2\,000$ | 无附加约束 | ||
| 5 分 | $1 \le N, Q \le 200\,000$ | 最初及每次事件后每种长度的木棍数量均为 $0, 1$ 或 $2$ | ||
| 5 分 | $1 \le N, Q \le 200\,000$ | 对于每个事件，满足 $ | d_i | = 1$ |
| 5 分 | $1 \le N, Q \le 200\,000$ | 无附加约束 |
输出格式
输出 $Q$ 行，每行包含一个整数，表示每次事件后的答案。
样例
输入 1
4 3 3 1 4 1 3 -3 1 6 2 1
输出 1
1 3 4
说明 1
第一次事件后，Alice 可以用长度为 $(1, 1, 1)$ 的木棍制作一个三角形。
第二次事件后，Alice 可以用长度为 $(1, 1, 1)$ 的木棍制作 3 个三角形。
第三次事件后，Alice 可以用长度为 $(1, 1, 1)$ 的木棍制作 3 个三角形，并用长度为 $(2, 2, 3)$ 的木棍制作一个三角形。