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

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

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

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

每次修改完成后，小庆都想知道这样画海底是否足够体现大海的深度。为此，小庆会通过如下过程给当前的海底折线打分。首先，对于每一段下标区间 $[i,j]$，小庆会求出该下标区间所对应的海底折线上深度最深的点的纵坐标，即 $a_i,a_{i+1},\dots ,a_j$ 中的最小值。然后，小庆会将所得结果对所有区间求和，即： $$\sum _{i=1}^n\sum _{j=i}^n\underset{k=i}{\overset{j}{min}}{a}_k$$ 然而，小庆的动作实在太慢了，眼看着小重就要吃完饭回来了，她只能请求你的帮忙。请帮助小庆执行这 $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\mathrm{\%}$ 的数据，$1\le n,m\le 2\times {10}^5,1\le a_i,w\le {10}^6,1\le x\le n$。

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

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

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

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

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

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

时间限制：$\mathtt{\text{8s}}$

空间限制：$\mathtt{\text{1GB}}$