Heavy rain (Easy)

Rain falls endlessly on $N$ cells in a row. Initially, cell $i$ has a wall of height $A_i$. When the water trapped inside a wall fills up, it overflows past the left and right ends and disappears. Rain does not move in any direction other than left and right along the row.

There are $Q$ queries. Each query consists of $i$ and $x$, meaning that from then on, the wall in cell $i$ has height $x$. It is guaranteed that $A_i < x$.

After each query, print the maximum amount of rain that can end up collecting.

The first line contains $N$ and $Q$ in that order ($1 \le N \le 100\,000$; $1 \le Q \le 100\,000$).

The second line contains the initial heights $A_1, A_2, \ldots, A_N$ in order ($1 \le A_i \le 10^9$).

Each of the next $Q$ lines contains two integers $i$ and $x$, separated by a space ($1 \le i \le N$; $1 \le x \le 10^9$).

All numbers in the input are integers.

Print $Q$ lines. The $k$-th line is the answer after the $k$-th query.