{"raw_statement":[{"iden":"statement","content":"Alice 有一些棍子。一开始，对于每个 $l=1, \\ldots, N$，她有 $c_{l}$ 根长度为 $l$ 的棍子。\n\nAlice 想用她的棍子做一些等腰三角形。一个等腰三角形由两根长度为 $l$ 的棍子和一根长度在 $1$ 和 $2 l-1$ 之间的棍子组成。注意，三根棍子的长度必须严格满足三角形不等式，等边三角形也是满足条件的。每根棍子最多只能在一个三角形里使用一次。Alice 想知道用她的棍子最多能做出多少等腰三角形。\n\n有 $Q$ 个事件改变了她拥有的棍子的数量。第 $i$ 个事件包含两个整数 $l_{i}$ 和 $d_{i}$，表示长度为 $l_{i}$ 的棍子的数量变化了 $d_{i}$。注意，$d_{i}$ 可以任意整数，但是 Alice 永远不会有负数或者超过 $10^{9}$ 根长度为 $l$ 的棍子。\n\n你需要求出在每个事件之后，Alice 用她的棍子最多能做出多少等腰三角形。"},{"iden":"input","content":"第一行包含两个用空格分隔的整数 $N$ 和 $Q$。\n\n第二行包含 $N$ 个用空格分隔的整数 $c_{1}, c_{2}, \\ldots, c_{N}$，表示 Alice 的开始时拥有的棍子。\n\n接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $l_{i}$ 和 $d_{i}$，表示一个事件。\n\n保证在每个事件之前和之后，对于每个 $l=1, \\ldots, N$，长度为 $l$ 的棍子的数量都在 $0$ 和 $10^{9}$ 之间。"},{"iden":"output","content":"输出 $Q$ 行，每行包含一个整数，表示每个事件之后的答案。"},{"iden":"note","content":"在第一个事件之后，Alice 可以用长度为 $ (1,1,1)$ 的棍子做一个三角形。\n\n在第二个事件之后，Alice 可以用长度为 $(1,1,1)$ 的棍子做三个三角形。\n\n在第三个事件之后，Alice 可以用长度为 $(1,1,1)$ 的棍子做三个三角形，并用长度为 $(2,2,3)$ 的棍子做一个三角形。\n\n对于所有的数据，有 $1 \\leq N, Q \\leq 2\\times 10^5$，$0 \\leq c_{i} \\leq 10^{9}$，$1 \\leq l_{i} \\leq N$，$-10^{9} \\leq d_{i} \\leq 10^{9}$。\n\n|子任务编号|\t分值|\tN, Q 的范围|\t额外限制|\n| :-: | :-: |:-:|:-:|\n|1|\t20|\t$1 \\leq N, Q \\leq 2000$|\t在所有时刻，总共最多有 $2000$ 根棍子。|\n|2|\t20|\t$1 \\leq N, Q \\leq 2000$|没有额外的限制|\n|3|\t20|\t$1 \\leq N, Q \\leq 2\\times 10^5$|\t在所有时刻，每种长度的棍子的数量只会是 $1,2,3$ |\n|4|\t20|\t$1 \\leq N, Q \\leq 2\\times 10^5$| $d_{i}=1,-1$ |\n|5|\t20| $1 \\leq N, Q \\leq 2\\times 10^5$|没有额外的限制|"}],"translated_statement":null,"sample_group":[["4 3\n3 1 4 1\n3 -3\n1 6\n2 1","1\n3\n4"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}