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

## 예제 입력 1

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


## 예제 출력 1

3
2
2


## 출처

• 문제를 만든 사람: yclock

## 채점 및 기타 정보

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