对于一个长度为 $m$ 的序列 $B$，按如下方式定义 $f(B)$。

• 构造另一个长度为 $m$ 的正整数序列 $C$。
• 您需要保证对于所有 $i \in [1,m]$，有 $1 \le C_i \le B_i$。
• 您需要保证对于所有 $i \in [1,m-1]$，有 $C_i \le C_{i+1}$，即 $C$ 为一单调不降序列。
• 您需要最大化序列 $C$ 中包含的不同元素个数。
• $f(B)$ 被定义成 $C$ 中包含的不同元素个数的最大可能值。
• 例子：若 $B=\{1,4,9,3\}$，令 $C=\{1,2,2,3\}$，$C$ 中有 $1,2,3$ 三个不同元素，且可以证明在所有合法的序列 $C$ 中，不同元素个数不会超过 $3$，故 $f(B)=3$。

给定一个长度为 $n$ 的序列 $A$，您需要进行 $q$ 次操作，每次操作给定两个整数 $p,x$，您需要做两件事情：

1. 您需要将 $A_p$ 修改为 $x$，注意此处的修改是永久性的，会影响后续的操作。
2. 求 $\sum_{i=1}^n\sum_{j=i}^n f(A_i,A_{i+1},\cdots,A_j)$。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数 $A_1,\cdots,A_n$。

接下来 $Q$ 行，每行两个整数 $p,x$，表示一次操作。

输出格式

输出 $Q$ 行，每行一个整数，依次回答每个操作后的问题。

样例

样例输入 #1

2 2
2 1
2 2
1 1

样例输出 #1

4
4

样例解释 #1

• 第一次询问，$A=[2,2]$，$f(\{2\})=1$，$f(\{2,2\})=2$，答案为 $1 \times 2+2=4$。
• 第二次询问，$A=[1,2]$，$f(\{1\})=f(\{2\})=1$，$f(\{1,2\})=2$，答案为 $1+1+2=4$。

样例输入 #2

5 2
2 2 1 4 2
5 1
3 4

样例输出 #2

19
25

其余样例见下发文件。

数据范围与约定

对于所有数据，有：

• $1 \le n,q \le 10^5$
• $1 \le A_i,p,x \le n$

子任务：