题目描述

译自 CCO 2023 Day2 T3「Triangle Collection」。

Alice 有一些棍子。一开始，对于每个 $\ell=1, \ldots, N$，她有 $c_{\ell}$ 根长度为 $\ell$ 的棍子。

Alice 想用她的棍子做一些等腰三角形。一个等腰三角形由两根长度为 $\ell$ 的棍子和一根长度在 $1$ 和 $2 \ell-1$ 之间的棍子组成。注意，三根棍子的长度必须严格满足三角形不等式，等边三角形也是满足条件的。每根棍子最多只能在一个三角形里使用一次。Alice 想知道用她的棍子最多能做出多少等腰三角形。

有 $Q$ 个事件改变了她拥有的棍子的数量。第 $i$ 个事件包含两个整数 $\ell_{i}$ 和 $d_{i}$，表示长度为 $\ell_{i}$ 的棍子的数量变化了 $d_{i}$。注意，$d_{i}$ 可以任意整数，但是 Alice 永远不会有负数或者超过 $10^{9}$ 根长度为 $\ell$ 的棍子。

你需要求出在每个事件之后，Alice 用她的棍子最多能做出多少等腰三角形。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $Q$。

第二行包含 $N$ 个用空格分隔的整数 $c_{1}, c_{2}, \ldots, c_{N}$，表示 Alice 的开始时拥有的棍子。

接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $\ell_{i}$ 和 $d_{i}$，表示一个事件。

保证在每个事件之前和之后，对于每个 $\ell=1, \ldots, N$，长度为 $\ell$ 的棍子的数量都在 $0$ 和 $10^{9}$ 之间。

输出格式

输出 $Q$ 行，每行包含一个整数，表示每个事件之后的答案。

4 3
3 1 4 1
3 -3
1 6
2 1

1
3
4

在第一个事件之后，Alice 可以用长度为 $(1,1,1)$ 的棍子做一个三角形。

在第二个事件之后，Alice 可以用长度为 $(1,1,1)$ 的棍子做三个三角形。

在第三个事件之后，Alice 可以用长度为 $(1,1,1)$ 的棍子做三个三角形，并用长度为 $(2,2,3)$ 的棍子做一个三角形。

数据范围与提示

对于所有的数据，有 $1 \leq N, Q \leq 2\times 10^5$，$0 \leq c_{i} \leq 10^{9}$，$1 \leq \ell_{i} \leq N$，$-10^{9} \leq d_{i} \leq 10^{9}$。