# [CCO2023] Triangle Collection

## 题目描述

Alice 有一些棍子。一开始，对于每个 $l=1, \ldots, N$，她有 $c_{l}$ 根长度为 $l$ 的棍子。

Alice 想用她的棍子做一些等腰三角形。一个等腰三角形由两根长度为 $l$ 的棍子和一根长度在 $1$ 和 $2 l-1$ 之间的棍子组成。注意，三根棍子的长度必须严格满足三角形不等式，等边三角形也是满足条件的。每根棍子最多只能在一个三角形里使用一次。Alice 想知道用她的棍子最多能做出多少等腰三角形。

有 $Q$ 个事件改变了她拥有的棍子的数量。第 $i$ 个事件包含两个整数 $l_{i}$ 和 $d_{i}$，表示长度为 $l_{i}$ 的棍子的数量变化了 $d_{i}$。注意，$d_{i}$ 可以任意整数，但是 Alice 永远不会有负数或者超过 $10^{9}$ 根长度为 $l$ 的棍子。

你需要求出在每个事件之后，Alice 用她的棍子最多能做出多少等腰三角形。

## 输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $Q$。

第二行包含 $N$ 个用空格分隔的整数 $c_{1}, c_{2}, \ldots, c_{N}$，表示 Alice 的开始时拥有的棍子。

接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $l_{i}$ 和 $d_{i}$，表示一个事件。

保证在每个事件之前和之后，对于每个 $l=1, \ldots, N$，长度为 $l$ 的棍子的数量都在 $0$ 和 $10^{9}$ 之间。

## 输出格式

输出 $Q$ 行，每行包含一个整数，表示每个事件之后的答案。

## 样例 #1

### 样例输入 #1

```
4 3
3 1 4 1
3 -3
1 6
2 1
```

### 样例输出 #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 l_{i} \leq N$，$-10^{9} \leq d_{i} \leq 10^{9}$。

|子任务编号|	分值|	N, Q 的范围|	额外限制|
| :-: | :-: |:-:|:-:|
|1|	20|	$1 \leq N, Q \leq 2000$|	在所有时刻，总共最多有 $2000$ 根棍子。|
|2|	20|	$1 \leq N, Q \leq 2000$|没有额外的限制|
|3|	20|	$1 \leq N, Q \leq 2\times 10^5$|	在所有时刻，每种长度的棍子的数量只会是 $1,2,3$ |
|4|	20|	$1 \leq N, Q \leq 2\times 10^5$| $d_{i}=1,-1$ |
|5|	20| $1 \leq N, Q \leq 2\times 10^5$|没有额外的限制|