시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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.

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

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.

서브태스크 1 (5점)

  • $N \le 50$
  • $Q \le 100$

서브태스크 2 (8점)

  • $N \le 10\,000$
  • $Q \le 25\,000$

서브태스크 3 (11점)

  • $A_i \le 10, h \le 10$

서브태스크 4 (7점)

  • Each adjustment only decreases the height of the streetlight.

서브태스크 5 (15점)

  • Once the streetlight had been adjusted to decrease its height, it will never be adjusted to increase its height.
  • Once the streetlight had been adjusted to increase its height, it will never be adjusted to decrease its height.

서브태스크 6 (12점)

  • $Q \le 8\,000$

서브태스크 7 (16점)

  • At most $8\,000$ different streetlights will have their height adjusted.

서브태스크 8 (21점)

  • $N \le 40\,000$
  • $Q \le 100\,000$

서브태스크 9 (55점)

  • No additional limits.

예제 입력 1

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

예제 출력 1

3
2
2

출처

  • 문제를 만든 사람: yclock

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.