I. Streetlights
time limit per test
5 s
memory limit per test
1024 mebibytes
input
standard input
output
standard output

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 two 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 \lt k \lt j$$$, $$$A_k \lt A_i$$$.

The city may adjust the height of a streetlight $$$Q$$$ times. Each adjustment is given as a pair of positive integers $$$(x, h)$$$, which indicates that the height of $$$x$$$-th streetlight was adjusted to $$$h$$$. In other words, $$$A_x = h$$$.

Before the updates, and also after each update, find the number of pairs $$$1 \le i \lt j \le N$$$ such that you can install an electric wire between streetlights $$$i$$$ and $$$j$$$.

Input

The first line contains two integers $$$N$$$ and $$$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$$$).

Each of the next $$$Q$$$ lines contains two integers $$$x$$$ and $$$h$$$, denoting that $$$A_x = h$$$ after the query ($$$1 \le x \le N$$$, $$$1 \le h \le 10^9$$$). It is guaranteed that $$$h$$$ is different from the height of the $$$x$$$-th streetlight immediately prior to the requested update.

Output

Output $$$Q+1$$$ lines. On the $$$i$$$-th line ($$$1 \le i \le Q + 1$$$), output the number of pairs you can install an electric wire between after processing the first $$$i - 1$$$ update queries.

Example
Input
6 2
4 2 2 2 4 6
4 6
6 4
Output
3
2
2