Street Lamps

Along a straight road, $N$ street lamps are installed. The initial height of the $i$-th lamp is $A_i$ ($1 \le i \le N$). You want to string electric wires between the lamps.

To hang a wire between lamp $i$ and lamp $j$ (where $i < j$), both of the following conditions must hold.

• $A_i = A_j$ (the two lamps have the same height).
• For every $k$ with $i < k < j$, $A_k < A_i$ (every lamp between them is shorter than both).

The administrator changes the heights of some lamps, and each change affects which wires can be hung. There are $Q$ height changes in total. Each change sets the height of the $x$-th lamp to $h$. After each change, count the pairs of lamps between which a wire can be hung.

The first line contains two integers $N$ and $Q$ ($2 \le N \le 100\,000$, $1 \le Q \le 250\,000$).

The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le 10^9$).

Each of the next $Q$ lines contains two integers $x$ and $h$ ($1 \le x \le N$, $1 \le h \le 10^9$), meaning $A_x$ is set to $h$. The height of lamp $x$ just before the change is guaranteed to differ from $h$.

Print the number of wires that can be hung in the initial state on the first line.

Then print, on each of the next $Q$ lines, the number of wires that can be hung after the corresponding height change.