가로등

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

$i$번 가로등과 $j( \gt i)$번 가로등 사이에 전기줄을 걸기 위해서는 다음 두 조건을 모두 만족해야 한다.

• $A\_i = A\_j$ (두 가로등의 높이가 같다.)
• 모든 $i < k < j$에 대하여, $A\_k < A\_i$이다. (두 가로등 사이에 있는 모든 가로등의 높이는 두 가로등보다 낮다.)

일부 가로등은 관리자의 판단에 따라 높이가 조정되며, 높이가 조정된 가로등으로 인해 전기줄을 걸 수 있는 상황이 변경된다. 

"$x$번째 가로등의 높이를 $h$로 변경"하는 높이 조정 작업은 총 $Q$번 행해진다. 가로등 높이 변경이 이루어질 때마다, 높이 조정 후 전기줄을 걸 수 있는 가로등 쌍의 개수를 계산하는 프로그램을 작성하고자 한다.

첫째 줄에 두 정수 $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$개의 줄에는 높이 조정 작업 각각에 대해, 높이 조정 후 가로등에 걸 수 있는 전기줄의 개수를 출력한다.