Stanley 决定购买一台由“Monoblock”公司制造的新台式电脑,要在他们的网站上解决验证码问题,他需要解决以下任务。
数组的厉害之处在于数组可以分割的连续相同数字的块的最小数量。例如,数组的神奇之处
- $$$[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$$$ 的所有子段中的 Awesomeness 值的总和。换句话说,在每次查询之后,您需要计算 $$$$$$\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]$$$ 的精彩程度。
输入
在第一行中,给出两个整数 $$$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$$$)。
输出
在新行上打印每个查询的答案。
示例
输入 #1
5 5 1 2 3 4 5 3 2 4 2 3 1 2 1 2 2
输出 #1
29 23 35 25 35
注意
在第一个查询之后 $$$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块;