小重喜欢画画。在他的素描本上，画着一幅他想象中的海底世界图景。

具体来说，素描本上有一条有 $n$ 个点连成的折线，折线上从左往右第 $i$ 个点是 $(i, a_i)$。这条折线象征着海底的轮廓。

趁小重中午去吃饭了，小庆拿着小重的素描本，开始端详起来。小庆觉得，小重画的海底折线是不完美的。

因此，小庆决定偷偷对这条海底折线进行 $m$ 次操作。每次操作时，小庆会选定 $x$ 和 $w$，然后将第 $x$ 个点的纵坐标 $a_i$ 改为 $w$。

每次修改完成后，小庆都想知道这样画海底是否足够体现大海的深度。为此，小庆会通过如下过程给当前的海底折线打分。首先，对于每一段下标区间 $[i, j]$，小庆会求出该下标区间所对应的海底折线上深度最深的点的纵坐标，即 $a_i, a_{i+1}, \dots, a_j$ 中的最小值。然后，小庆会将所得结果对所有区间求和，即： \begin{equation} \sum_{i=1}^n\sum_{j=i}^n\min_{k=i}^j a_k \end{equation} 然而，小庆的动作实在太慢了，眼看着小重就要吃完饭回来了，她只能请求你的帮忙。请帮助小庆执行这 $m$ 次操作，并在每次操作后输出上面这一求和式的值。

输入格式

第一行，两个整数，表示 $n,m$。

第二行，$n$ 个整数，表示 $a_1, \dots, a_n$。

接下来 $m$ 行，每行两个整数，分别表示一次修改中的 $x,w$。

输出格式

共 $m$ 行，依次表示每次修改后的答案。

样例一

input

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

output

23
23
25
29
29

数据范围

对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5,1\le a_i,w\le 10^6,1\le x\le n$。

$\operatorname{Subtask} 1(10\%):n,m\le 5\times 10^3$。

$\operatorname{Subtask} 2(15\%):n,m\le 10^5$，$a_i,w\le 10$。

$\operatorname{Subtask} 3(15\%):n,m\le 10^5$，保证 $a_i,w$ 在 $[1,10^6]$ 内均匀随机，$x$ 在 $[1,n]$ 内均匀随机。

$\operatorname{Subtask} 4(30\%):n,m\le 10^5$。

$\operatorname{Subtask} 5(20\%):n,m\le 1.5\times 10^5$。

$\operatorname{Subtask} 6(10\%):$ 无特殊限制。

时间限制：$\texttt{8s}$

空间限制：$\texttt{1GB}$