There are $N$ streetlights installed along a straight road. The initial height of the $i$-th streetlight is $A_i$ ($1 \le i \le N$). We intend to install electric cables using these streetlights.

To install a cable between the $i$-th streetlight and the $j$-th streetlight ($j > i$), both of the following conditions must be satisfied:

• $A_i = A_j$ (The heights of the two streetlights are equal.)
• For all $i < k < j$, $A_k < A_i$. (All streetlights between the two streetlights are shorter than the two streetlights.)

Some streetlights have their heights adjusted based on the administrator's decision, and the situation regarding where cables can be installed changes due to these adjusted heights.

There are a total of $Q$ height adjustment operations, each of which is "change the height of the $x$-th streetlight to $h$". We want to write a program that calculates the number of pairs of streetlights between which a cable can be installed after each height adjustment.

Implementation Details

You must implement the following function:

vector<long long int> count_cable(vector<int> A, vector< pair<int, int> > C)

• This function is called exactly once.
• The size of the given array $A$ is $N$. Each element of array $A$ represents the initial height of the streetlights. In other words, $A[i] = A_{i+1}$ ($0 \le i \le N - 1$).
• $C$ is an array consisting of $Q$ ordered pairs $(x, h)$, where each pair $(x, h)$ represents the operation "change the height of the $x$-th streetlight to $h$".
• This function must return an integer array of size $Q+1$, which stores the number of cables that can be installed on the initially installed streetlights, and the number of cables that can be installed after each of the $Q$ height adjustment operations.

You must not execute any input/output functions in any part of the submitted source code.

Constraints

• $2 \le N \le 100\,000$
• $1 \le Q \le 250\,000$
• The height of every streetlight is always an integer between $1$ and $10^9$.
• In an adjustment operation to change the height of the $x$-th streetlight to $h$, $1 \le x \le N$, and it is guaranteed that the height of the $x$-th streetlight changes. That is, the height of the $x$-th streetlight immediately before the adjustment is different from $h$.

Subtasks

1. (5 points)
   • $N \le 50$
   • $Q \le 100$
2. (8 points)
   • $N \le 10\,000$
   • $Q \le 25\,000$
3. (11 points)
   • The height of all streetlights is always $10$ or less.
4. (7 points)
   • All height adjustment operations decrease the height of the streetlight.
5. (15 points)
   • Once a streetlight's height increases, it does not decrease afterwards.
   • Once a streetlight's height decreases, it does not increase afterwards.
6. (12 points)
   • $Q \le 8\,000$
7. (16 points)
   • The total number of streetlights whose height changes at least once is $8\,000$ or less.
8. (21 points)
   • $N \le 40\,000$
   • $Q \le 100\,000$
9. (55 points)
   • No additional constraints.

Note

The score for each subtask is the minimum score among all data for that subtask.

Examples

Consider the case where $A = [4, 2, 2, 2, 4, 6]$ and $C = [(4, 6), (6, 4)]$. $C = [(4, 6), (6, 4)]$ means that in the first height adjustment, the height of the 4th streetlight is changed to $6$, and in the second height adjustment, the height of the 6th streetlight is changed to $4$.

The grader calls the following function:

count_cable([4,2,2,2,4,6], [(4,6),(6,4)])

The image below shows the situation of cables that can be installed on the 6 streetlights installed in the initial state. As shown in the figure, a total of 3 cables can be installed.

The image below shows the situation of cables that can be installed after changing the height of the 4th streetlight to 6 according to the first height adjustment operation. As shown in the figure, a total of 2 cables can be installed.

The image below shows the situation of cables that can be installed after changing the height of the 6th streetlight to 4 according to the second height adjustment operation. Similarly, a total of 2 cables can be installed.

The function count_cable must finally return [3, 2, 2]. This example satisfies the conditions of all subtasks except subtask 4.

Sample grader

The sample grader receives input in the following format:

• Line 1: $N$ $Q$
• Line 2: $A_1$ $A_2$ $\dots$ $A_N$
• Line 2 + $i$ ($1 \le i \le Q$): $x_i$ $h_i$

$(x_i, h_i)$ is an ordered pair representing the $i$-th height adjustment operation ($1 \le i \le Q$).

The sample grader outputs in the following format:

• Line 1: The array returned by the function count_cable

Note that the sample grader is different from the grader used in actual grading.