Maximizing Isosceles Triangles

Alice has some sticks. Initially, for each integer \(l = 1, \ldots, N\) she has \(c_l\) sticks of length \(l\). She wishes to form as many isosceles triangles as possible. An isosceles triangle is formed by taking two sticks of some length \(l\) (the equal sides) together with a third stick (the base) of some length \(b\) satisfying \(1 \le b \le 2l-1\).

Note that the three sticks must strictly satisfy the triangle inequality. (An equilateral triangle obviously satisfies the condition.) Also, each stick may be used in at most one triangle.

There are \(Q\) update events. In the \(i\)th event, two integers \(l_i\) and \(d_i\) are given indicating that the number of sticks of length \(l_i\) changes by \(d_i\) (\(d_i\) may be positive or negative). It is guaranteed that for every length the number of sticks never becomes negative or exceeds \(10^9\).

After each event, determine the maximum number of isosceles triangles Alice can make.

---

Triangle formation note: A triangle formed using two sticks of length \(l\) and a base stick of length \(b\) must satisfy:

[ \begin{cases} l + l > b,\ l + b > l,\ l + b > l, \end{cases} ]

Since \(l+l > b\) is equivalent to \(b < 2l\) and we require \(1 \le b \le 2l-1\), the triangle inequality automatically holds if the base is chosen in the allowed range.

Input/Output details: See below.

inputFormat

The first line contains two integers \(N\) and \(Q\) \((1 \le N \le \text{small},\; Q \ge 1)\) — the number of distinct stick lengths and the number of events.

The second line contains \(N\) integers \(c_1, c_2, \ldots, c_N\) where \(c_l\) is the initial number of sticks of length \(l\).

Then \(Q\) lines follow. Each of these lines contains two integers \(l_i\) and \(d_i\) \((1 \le l_i \le N,\; |d_i| \ge 0)\) representing an update: the number of sticks of length \(l_i\) changes by \(d_i\). It is guaranteed that after every update, the count for each length remains between 0 and \(10^9\) inclusive.

outputFormat

After each event, output a single line containing the maximum number of isosceles triangles that can be formed using the sticks available at that moment.

sample

3 3
1 2 3
1 1
2 -1
3 2

2
1
2

</p>