Dadas is preparing to propose to Woohyun. In the past, he just ended it with an "I like you," but now, he plans to show his true feelings by preparing many jewels with special care.

Dadas sets up pillars at integer coordinates from $0$ to $N$ on a number line and places jewels on them. The height of the pillar at coordinate $i$ is $A_i$. If $A_i = 0$, the jewel is placed on the ground. Therefore, there is a total of $N+1$ jewels, and the position of each jewel is at coordinate $i$ with height $A_i$.

Dadas wants to install lights so that all the jewels can be illuminated. Each light illuminates the area downwards within a $45$-degree angle to the left and right from its installed position, including the boundaries. Shadows casted by the pillars are ignored.

The lights are installed at positive integer heights at integer coordinates from $0$ to $N$ on the number line. They can be installed regardless of the heights of the pillar and jewel at the corresponding coordinate. The installation cost of each light is equal to its height. The total installation cost of the lights is equal to the sum of the installation costs of each light.

The figure below is an example showing a state where the light does not reach some jewels. Such installation is not allowed.

On the other hand, the figure below is an example of a possible installation of lights where all jewels are illuminated by the lights.

Dadas gives commands $Q$ times as follows.

• x y : Change the value of $A_x$ to $y$.\end{itemize} Find the minimum installation cost in the initial state. Then, print the minimum total installation cost of the lights after each of the $Q$ given commands.

The input is given in the following format.

$N \ Q$ $A_0 \ A_1 \ \cdots \ A_N$ $x_1 \ y_1$ $x_2 \ y_2$ $\vdots$ $x_Q \ y_Q$

Print $Q+1$ lines. Every line should contain one integer: $i$-th line contains the minimum total installation cost of the lights after $i-1$ commands.

• $2 \le N \le 200\ 000$.
• $1 \le Q \le 200\ 000$.
• $0 \le A_i \le \min(N-i,i)$ ($0 \le i \le N$).
• $0 \leq x_i \leq N$ ($1 \leq i \leq Q$).
• $0 \leq y_i \leq \min(N - x_i, x_i)$ ($1\leq i \leq Q$).