题目描述

译自 $CCO$ $2023$ $Day2$ $T3$「$Triangle$ $Collection$」。

Alice 拥有若干棍子，初始时对于每个 $\ell=1, \ldots, N$，她有 $c_{\ell}$ 根长度为 $\ell$ 的棍子。

Alice 想用这些棍子制作等腰三角形，等腰三角形的定义为：由两根长度为 $\ell$ 的棍子，和一根长度在 $1$ 到 $2\ell-1$ 之间的棍子组成。三根棍子需严格满足三角形不等式，等边三角形也符合条件。每根棍子最多只能用于一个三角形。

存在 $Q$ 个事件改变棍子数量，第 $i$ 个事件包含 $\ell_i$ 和 $d_i$，表示长度为 $\ell_i$ 的棍子数量变化 $d_i$（$d_i$ 可为任意整数，且事件前后所有长度的棍子数量均在 $0$ 到 $10^9$ 之间）。

你的任务是在每个事件后，计算 Alice 最多能做出的等腰三角形数量。

输入格式

• 第一行：两个整数 $N$ 和 $Q$（空格分隔）。
• 第二行：$N$ 个整数 $c_1, c_2, \ldots, c_N$（空格分隔），表示初始时各长度棍子的数量。
• 接下来 $Q$ 行：每行两个整数 $\ell_i$ 和 $d_i$（空格分隔），表示一个修改事件。

输出格式

输出 $Q$ 行，每行一个整数，表示对应事件后的最大等腰三角形数量。

样例

输入

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

输出

1
3
4

说明

1. 第一个事件后：可使用长度为 $(1,1,1)$ 的棍子制作 $1$ 个三角形。
2. 第二个事件后：可使用长度为 $(1,1,1)$ 的棍子制作 $3$ 个三角形。
3. 第三个事件后：可制作 $3$ 个 $(1,1,1)$ 的三角形，以及 $1$ 个 $(2,2,3)$ 的三角形，共 $4$ 个。

数据范围与提示

• 所有数据：$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$。
• 子任务信息如下：