|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|4 초||1024 MB||24||5||3||20.000%|
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 some streetlights. To install an electric wire between the streetlights $i$ and $j( \gt i)$, the following conditions must be satisfied.
You are interested in a number of pairs $1 \le i < j \le N$ which you can install an electric wire between the streetlight $i$ and $j$.
In addition, the city may adjust the height of some streetlight for $Q$ times. Each adjustments are given as a pair of positive integer $(x, h)$, which indicates that the height of $x$-th streetlight was adjusted to $h$. In other words, $A_x = h$. After each queries, you should find the updated number of pairs which you can install an electric wire between.
The first line contains two integers $N, 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$)
The next $Q$ lines contain two integers $x, h$, denoting that $A_x = h$ after the query ($1 \le x \le N, 1 \le h \le 10^9$). It is guaranteed that the $h$ is different from the original height of $x$-th streetlight.
In the first line, print the number of pairs which you can install an electric wire between.
In the next $Q$ lines, print the number of pairs which you can install an electric wire between, after each updates.
In total, you have to print $Q+1$ integers.
6 2 4 2 2 2 4 6 4 6 6 4
3 2 2