삼각형 모음

처음에 앨리스는 각 $\ell = 1, \ldots, N$에 대해 길이가 $\ell$인 막대기를 $c_{\ell}$개 가지고 있다.

앨리스는 이 막대기들로 이등변삼각형을 만들려고 한다. 이등변삼각형은 길이가 $\ell$로 같은 막대기 두 개와, 길이가 1 이상 $2\ell - 1$ 이하인 막대기 하나로 이루어진다. 삼각형은 삼각형 부등식을 엄격히 만족해야 하며, 정삼각형도 허용된다. 각 막대기는 최대 한 개의 삼각형에만 쓸 수 있다. 앨리스가 만들 수 있는 이등변삼각형의 최대 개수를 구한다.

막대기 모음을 바꾸는 사건이 $Q$개 주어진다. $i$번째 사건은 정수 $\ell_i$와 $d_i$로 이루어지며, 길이가 $\ell_i$인 막대기의 개수가 $d_i$만큼 변한다는 뜻이다. $d_i$는 양수, 음수, 0일 수 있으나, 앨리스가 가진 막대기 개수가 음수가 되거나 어느 길이에서든 $10^9$개를 넘는 일은 없다.

각 사건 후에, 앨리스가 막대기를 최적으로 사용했을 때 만들 수 있는 이등변삼각형의 최대 개수를 구한다.

첫 줄에 정수 $N$과 $Q$가 주어진다.

둘째 줄에 정수 $c_1, c_2, \ldots, c_N$ ($0 \le c_i \le 10^9$)이 주어진다.

이어지는 $Q$개의 줄에는 각각 정수 $\ell_i$와 $d_i$ ($1 \le \ell_i \le N$, $-10^9 \le d_i \le 10^9$)가 주어진다.

$Q$개의 줄을 출력한다. 각 줄에는 해당 사건 후의 답을 정수 하나로 쓴다.

$1 \le N, Q \le 200{,}000$

초기 상태와 각 사건 후에, 모든 $\ell$에 대해 길이가 $\ell$인 막대기의 개수는 0 이상 $10^9$ 이하이다.