题目描述

有 $N$ 个人从左到右站在位置 $1,2,\ldots,N$，每个人都张着嘴。第 $i$ 个人的饥饿度为 $A_i$。

你有无限多颗糖。你可以恰好进行一次以下过程：

1. 选择一个位置 $x$，站到该位置；
2. 将以下操作重复任意次（也可以一次都不执行）：
   • 若当前位于位置 $y$，移动到 $y-1$、$y$ 或 $y+1$ 中的一个位置；移动后的位置必须仍在 $1$ 到 $N$ 之间；
   • 向当前位置的人的嘴里投入一颗糖。

设第 $i$ 个人最终得到的糖果数为 $B_i$。你的目标是最小化

接下来有 $Q$ 次更新。第 $j$ 次更新给出 $i,v$，将 $A_i$ 永久修改为 $v$。每次更新后，求上述最小值。

限制条件

• $1\le N\le 10^5$
• $1\le Q\le 10^5$
• $0\le A_i\le 10^9$
• 每次更新中 $1\le i\le N$，$0\le v\le 10^9$
• 所有输入均为整数。

部分分

• 对满足 $Q\le 10$ 的数据求解正确，可获得 $2$ 分。

输入

N Q
A_1 A_2 ... A_N
i_1 v_1
i_2 v_2
...
i_Q v_Q

输出

输出 $Q$ 行。第 $j$ 行输出第 $j$ 次更新后的答案。

样例输入 1

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

样例输出 1

1
2
1

第一次更新后 $A=(1,0,0,2)$。例如，可以从位置 $3$ 开始，移动到位置 $4$ 并连续向第 $4$ 个人投两颗糖，得到 $B=(0,0,0,2)$，此时代价为 $1$。

样例输入 2

10 9
1 0 0 0 0 0 4 0 0 2
3 2
7 0
1 9
6 4
1 1
10 0
1 0
6 0
5 7

样例输出 2

5
3
3
5
5
3
2
0
1