题目背景

摩天大楼，太稀有，人人高贵富有；粉饰骷髅，气质有，人们争先恐后。

摩天大楼，想拥有，让人爱不释手；晶莹剔透，攀比后，才能高枕无忧。

题目描述

Wa1 邀请 ChA 来到一个神秘的二维空间。

这个空间中共矗立着 $n$ 栋摩天大楼，坐标 $i$（$1 \le i \le n$）处矗立着一栋高为 $a_i$ 的摩天大楼。由于该空间的科技水平远超人类，第 $i$ 栋大楼只会阻挡高度恰好等于 $a_i$ 的飞行物，其他高度的飞行物可以自由通过。

Wa1 为 ChA 准备了一架可飞行于正整数高度的飞机。每次游戏给定起点 $x$ 和终点 $y$（$1 \le x < y \le n$）。Wa1 会选择一个整数 $k$（$x \le k < y$），ChA 只能在第 $k$ 和第 $k+1$ 栋大楼之间改变飞行高度。

为保证安全，ChA 会采用以下策略：

• 从起点 $x$ 出发，以能不改变高度穿过区间 $[x,k]$ 所有大楼的最低高度飞行；
• 到达 $k$ 后，如有需要，再调整到能不改变高度穿过区间 $[k+1,y]$ 所有大楼的最低高度继续飞行，抵达终点 $y$。

若 ChA 在这次飞行中改变了一次高度，则会消耗 $1$ 单位航油。Wa1 是个卖航油的商人，为了赚取 ChA 的航油费，他会尽量让 ChA 在飞行中必须改变一次高度。

Wa1 邀请 ChA 游玩超值飞行套餐。具体地，设起点和终点为 $x,y$ 最多耗费 $f(x,y)$ 单位的航油，超值飞行套餐可以让 Wa1 卖出 $\displaystyle \sum_{i=1}^{n}\sum_{j=i+1}^{n}f(i,j)$ 单位的航油。

Wa1 共 $q$ 次邀请 ChA 来游玩超值飞行套餐，第 $i$ 次邀请前他会把 $x_i$ 处的大楼高度修改为 $v_i$。对于每次邀请，Wa1 想知道他能卖出去多少单位航油。

输入格式

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

第二行，$n$ 个正整数 $a_1, \ldots, a_n$，含义见题目描述。

接下来 $q$ 行，每行两个正整数 $x_i,v_i$，表示第 $x_i$ 栋大楼高度修改为 $v_i$。

输出格式

共 $q$ 行，每行一个整数，表示答案。

5 3
1 2 2 1 3
2 1
5 1
3 4

9
8
4

提示

【样例解释 #1】

初始高度：$\langle 1, 2, 2, 1, 3\rangle$。

对于第 $1$ 次操作：修改 $a_2 = 1$，新高度为 $\langle 1, 1, 2, 1, 3\rangle$。

• 若相邻两段可通过的最低高度不同，则 ChA 必须升降一次。
• 例如区间 $[1,5]$：选择 $k=2$，则通过 $[1,2]$ 的最低高度为 $2$，通过 $[3,5]$ 的最低高度为 $4$。显然 $2\neq4$，ChA 必须更改一次飞机高度，产生 $1$ 单位的耗油量。
• 统计可得总耗油量为 $9$ 单位。

【样例 #2】

见选手目录下的 $\textbf{\textit{building/building2.in}}$ 与 $\textbf{\textit{building/building2.ans}}$。

该样例满足测试点 $1$ 的约束条件。

【样例 #3】

见选手目录下的 $\textbf{\textit{building/building3.in}}$ 与 $\textbf{\textit{building/building3.ans}}$。

该样例满足测试点 $4\sim 7$ 的约束条件。

【样例 #4】

见选手目录下的 $\textbf{\textit{building/building4.in}}$ 与 $\textbf{\textit{building/building4.ans}}$。

该样例满足测试点 $8$ 的约束条件。

【样例 #5】

见选手目录下的 $\textbf{\textit{building/building5.in}}$ 与 $\textbf{\textit{building/building5.ans}}$。

该样例满足测试点 $9, 10$ 的约束条件。

【样例 #6】

见选手目录下的 $\textbf{\textit{building/building6.in}}$ 与 $\textbf{\textit{building/building6.ans}}$。

该样例满足测试点 $11, 12$ 的约束条件。

【样例 #7】

见选手目录下的 $\textbf{\textit{building/building7.in}}$ 与 $\textbf{\textit{building/building7.ans}}$。

该样例满足测试点 $16\sim 20$ 的约束条件。

【数据范围】

本题共 $20$ 个测试点，每个 $5$ 分。

对于所有测试数据，保证：

• $2\le n\le 10^6$，$1\le q\le 10^6$；
• $1\le x_i\le n$；
• $1\le a_i,v_i\le 10^6$。

::cute-table{tuack} |测试点编号|$n,q\le$|特殊性质| |:--:|:--:|:--:| |$1$|$80$|无| |$2, 3$|$300$|^| |$4\sim 7$|$5\times 10^3$|^| |$8$|$10^6$|A| |$9, 10$|^|B| |$11, 12$|^|C| |$13\sim 15$|^|D| |$16\sim 20$|^|无|

特殊性质 A：任意时刻不存在高度为 $1$ 的大楼。
特殊性质 B：任意时刻高度为 $1$ 的大楼最多存在一个。
特殊性质 C：任意时刻不存在高度为 $2$ 的大楼。
特殊性质 D：$q = 1$。