가로등

일직선 도로를 따라 $N$개의 가로등이 세워져 있다. $i$번째 가로등의 초기 높이는 $A_i$이다 ($1 \le i \le N$). 이 가로등을 이용해 전기줄을 설치하려고 한다.

$i$번 가로등과 $j$번 가로등($i < j$) 사이에 전기줄을 걸려면 다음 두 조건을 모두 만족해야 한다.

• $A_i = A_j$ (두 가로등의 높이가 같다.)
• 모든 $i < k < j$에 대하여 $A_k < A_i$이다. (두 가로등 사이에 있는 모든 가로등의 높이는 두 가로등보다 낮다.)

관리자가 일부 가로등의 높이를 조정하면 전기줄을 걸 수 있는 상황도 달라진다. 높이 조정은 총 $Q$번 이루어진다. 각 조정은 $x$번째 가로등의 높이를 $h$로 바꾼다. 조정할 때마다, 전기줄을 걸 수 있는 가로등 쌍의 개수를 구하시오.

첫째 줄에 두 정수 $N$, $Q$가 주어진다 ($2 \le N \le 100\,000$, $1 \le Q \le 250\,000$).

둘째 줄에 $N$개의 정수 $A_1, A_2, \ldots, A_N$가 주어진다 ($1 \le A_i \le 10^9$).

다음 $Q$개의 줄에는 두 정수 $x$, $h$가 주어지며, 이는 $A_x$를 $h$로 바꾼다는 뜻이다 ($1 \le x \le N$, $1 \le h \le 10^9$). 조정 직전 $x$번째 가로등의 높이는 $h$와 다르다고 보장된다.

첫째 줄에 초기 상태에서 전기줄을 걸 수 있는 개수를 출력한다.

다음 $Q$개의 줄에는 각 높이 조정 후 전기줄을 걸 수 있는 개수를 한 줄에 하나씩 출력한다.