409545: GYM103627 I Streetlights

There are $$$N$$$ streetlights along the straight road. The initial height of the $$$i$$$-th streetlight is a positive integer $$$A_i$$$ $$$(1 \le i \le N)$$$.

You are trying to install an electric wire between two streetlights. To install an electric wire between the streetlights $$$i$$$ and $$$j(> i)$$$, the following conditions must be satisfied:

• $$$A_i = A_j$$$,
• For every $$$i < k < j$$$, $$$A_k < A_i$$$.

The city may adjust the height of a streetlight $$$Q$$$ times. Each adjustment is given as a pair of positive integers $$$(x, h)$$$, which indicates that the height of $$$x$$$-th streetlight was adjusted to $$$h$$$. In other words, $$$A_x = h$$$.

Before the updates, and also after each update, find the number of pairs $$$1 \le i < j \le N$$$ such that you can install an electric wire between streetlights $$$i$$$ and $$$j$$$.

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

The next 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$$$, denoting that $$$A_x = h$$$ after the query ($$$1 \le x \le N$$$, $$$1 \le h \le 10^9$$$). It is guaranteed that $$$h$$$ is different from the height of the $$$x$$$-th streetlight immediately prior to the requested update.

Output $$$Q+1$$$ lines. On the $$$i$$$-th line ($$$1 \le i \le Q + 1$$$), output the number of pairs you can install an electric wire between after processing the first $$$i - 1$$$ update queries.

6 2
4 2 2 2 4 6
4 6
6 4

3
2
2