CF1715C.Monoblock

Stanley has decided to buy a new desktop PC made by the company "Monoblock", and to solve captcha on their website, he needs to solve the following task.

The awesomeness of an array is the minimum number of blocks of consecutive identical numbers in which the array could be split. For example, the awesomeness of an array

• $[1, 1, 1]$ is $1$;
• $[5, 7]$ is $2$, as it could be split into blocks $[5]$ and $[7]$;
• $[1, 7, 7, 7, 7, 7, 7, 7, 9, 9, 9, 9, 9, 9, 9, 9, 9]$ is 3, as it could be split into blocks $[1]$, $[7, 7, 7, 7, 7, 7, 7]$, and $[9, 9, 9, 9, 9, 9, 9, 9, 9]$.

You are given an array $a$ of length $n$. There are $m$ queries of two integers $i$, $x$. A query $i$, $x$ means that from now on the $i$-th element of the array $a$ is equal to $x$.

After each query print the sum of awesomeness values among all subsegments of array $a$. In other words, after each query you need to calculate $$\sum\limits_{l = 1}^n \sum\limits_{r = l}^n g(l, r),$$ where $g(l, r)$ is the awesomeness of the array $b = [a_l, a_{l + 1}, \ldots, a_r]$.

斯坦利决定购买一台由“Monoblock”公司生产的新台式电脑，为了在该公司网站上通过验证码，他需要解决以下问题。

一个数组的“酷炫值”（awesomeness）是指将该数组划分为若干个连续相同数字组成的块时，所需块数的最小值。例如：

• 数组 $[1, 1, 1]$ 的酷炫值为 $1$；
• 数组 $[5, 7]$ 的酷炫值为 $2$，因为它可被划分为块 $[5]$ 和 $[7]$；
• 数组 $[1, 7, 7, 7, 7, 7, 7, 7, 9, 9, 9, 9, 9, 9, 9, 9, 9]$ 的酷炫值为 $3$，因为它可被划分为块 $[1]$、$[7, 7, 7, 7, 7, 7, 7]$ 和 $[9, 9, 9, 9, 9, 9, 9, 9, 9]$。

给定一个长度为 $n$ 的数组 $a$。接下来有 $m$ 个查询，每个查询包含两个整数 $i$ 和 $x$。查询 $i$, $x$ 表示从此时起，将数组 $a$ 的第 $i$ 个元素修改为 $x$。

每次查询后，请输出数组 $a$ 的所有子段（subsegment）的酷炫值之和。换言之，每次查询后你需要计算

$$\sum\limits_{l = 1}^n \sum\limits_{r = l}^n g(l, r),$$

其中 $g(l, r)$ 表示子数组 $b = [a_l, a_{l + 1}, \ldots, a_r]$ 的酷炫值。

In the first line you are given with two integers $n$ and $m$ ($1 \leq n, m \leq 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the array $a$.

In the next $m$ lines you are given the descriptions of queries. Each line contains two integers $i$ and $x$ ($1 \leq i \leq n$, $1 \leq x \leq 10^9$).

第一行给出两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）—— 数组 $a$。

接下来 $m$ 行，每行给出一个查询的描述。每行包含两个整数 $i$ 和 $x$（$1 \leq i \leq n$, $1 \leq x \leq 10^9$）。

Print the answer to each query on a new line.

将每个查询的答案打印在新的一行上。

After the first query $a$ is equal to $[1, 2, 2, 4, 5]$, and the answer is $29$ because we can split each of the subsegments the following way:

1. $[1; 1]$: $[1]$, 1 block;
2. $[1; 2]$: $[1] + [2]$, 2 blocks;
3. $[1; 3]$: $[1] + [2, 2]$, 2 blocks;
4. $[1; 4]$: $[1] + [2, 2] + [4]$, 3 blocks;
5. $[1; 5]$: $[1] + [2, 2] + [4] + [5]$, 4 blocks;
6. $[2; 2]$: $[2]$, 1 block;
7. $[2; 3]$: $[2, 2]$, 1 block;
8. $[2; 4]$: $[2, 2] + [4]$, 2 blocks;
9. $[2; 5]$: $[2, 2] + [4] + [5]$, 3 blocks;
10. $[3; 3]$: $[2]$, 1 block;
11. $[3; 4]$: $[2] + [4]$, 2 blocks;
12. $[3; 5]$: $[2] + [4] + [5]$, 3 blocks;
13. $[4; 4]$: $[4]$, 1 block;
14. $[4; 5]$: $[4] + [5]$, 2 blocks;
15. $[5; 5]$: $[5]$, 1 block;

which is $1 + 2 + 2 + 3 + 4 + 1 + 1 + 2 + 3 + 1 + 2 + 3 + 1 + 2 + 1 = 29$ in total.

第一次查询后，$a$ 变为 $[1, 2, 2, 4, 5]$，答案为 $29$，因为我们可以将每个子段按如下方式划分：

1. $[1; 1]$: $[1]$，1 个块；
2. $[1; 2]$: $[1] + [2]$，2 个块；
3. $[1; 3]$: $[1] + [2, 2]$，2 个块；
4. $[1; 4]$: $[1] + [2, 2] + [4]$，3 个块；
5. $[1; 5]$: $[1] + [2, 2] + [4] + [5]$，4 个块；
6. $[2; 2]$: $[2]$，1 个块；
7. $[2; 3]$: $[2, 2]$，1 个块；
8. $[2; 4]$: $[2, 2] + [4]$，2 个块；
9. $[2; 5]$: $[2, 2] + [4] + [5]$，3 个块；
10. $[3; 3]$: $[2]$，1 个块；
11. $[3; 4]$: $[2] + [4]$，2 个块；
12. $[3; 5]$: $[2] + [4] + [5]$，3 个块；
13. $[4; 4]$: $[4]$，1 个块；
14. $[4; 5]$: $[4] + [5]$，2 个块；
15. $[5; 5]$: $[5]$，1 个块；

总和为 $1 + 2 + 2 + 3 + 4 + 1 + 1 + 2 + 3 + 1 + 2 + 3 + 1 + 2 + 1 = 29$。