题目描述

Aurora 和 Bianca 特别喜欢意大利杏仁饼干，今天，她们的爷爷烤了一大堆饼干（形成一个栈）。为了分这些饼干，她们发明了以下游戏。只要栈里还有饼干，她们就重复以下步骤：

• Aurora 选一个整数 $X \geq 0$。
• 接下来，Bianca 选一个整数 $Y \geq 0$，满足：
  • 剩下的饼干至少有 $Y$ 个，并且
  • $Y \neq X$。
• 然后 Aurora 吃掉最顶上的 $Y$ 个饼干（如果 $Y=0$ 就不吃）。
• 最后，如果还有剩下的饼干，Bianca 会吃掉最顶上的那一块。

当然，两个女生都想吃得越多越好。栈里的每块饼干都有一个重量 $1 \leq W_i \leq 50$。当所有饼干被吃完后，每个人的幸福度等于她在游戏中吃掉的所有饼干的重量总和。两个女生都知道如何最优地玩这个游戏——每个人总是会做出能让自己的最终幸福度最大化的选择。

因为这个游戏太好玩了，她们现在每天都要玩！在接下来的 $Q$ 天里，她们的爷爷每天都会烤一堆同样数量的饼干。为了让游戏更有趣，爷爷每天会改变其中一块饼干的重量，而其他饼干的重量保持不变。

对于初始的饼干堆，以及在每天进行改变之后，你需要计算出每天游戏结束时 Bianca 的幸福度。

输入格式

输入的第一行包含两个整数 $N$ 和 $Q$，分别是饼干的数量和变更的次数。饼干从上到下编号为 $0$ 到 $N-1$。

第二行包含 $N$ 个整数 $W_0, W_1, \dots, W_{N-1}$，即饼干的初始重量。

接下来的 $Q$ 行中，第 $i$ 行包含两个整数 $P_i$ 和 $Z_i$，描述第 $i$ 次变更：爷爷将第 $P_i$ 块饼干的重量改为 $Z_i$。换句话说，$W_{P_i}$ 的值变成了 $Z_i$。

输出格式

输出 $Q + 1$ 个整数，即每天游戏结束后 Bianca 的幸福度。

2 1
10 15
1 1

10
1

5 2
1 1 1 1 2
2 20
3 30

3
4
24

4 2
1 2 4 8
3 2
2 3

7
4
4

3 0
1 1 1

1

3 4
50 8 1
1 1
1 8
2 7
2 1

8
1
8
8
8

提示

样例解释

第一个样例。 第一天，饼干的重量分别是 $10$ 和 $15$。

• Aurora 选择 $X=1$ 是最优的。然后，Bianca 选择 $Y = 0$ 并吃掉最顶上的饼干。
• 在第二回合，Aurora 选择 $X = 0$。Bianca 唯一的选择是 $Y=1$。然后，Aurora 吃掉重量为 $15$ 的饼干，游戏结束。

第二天，第 $1$ 号饼干的重量变为 $1$，此时饼干的重量为 $[10, 1]$。

• Aurora 选择 $X=0$ 是最优的。然后，Bianca 选择 $Y = 1$。Aurora 吃掉最顶上的饼干，Bianca 吃掉剩下的一块。

游戏结束后，Bianca 的幸福度为 $1$。

第二个样例。 初始时，从上到下的饼干重量为 $[1,1,1,1,2]$。

• Aurora 选择 $X = 0$ 是最优的。Bianca 选择 $Y = 1$。Aurora 吃掉第一块，Bianca 吃掉第二块。
• 下一回合，Aurora 选择 $X = 0$。Bianca 选择 $Y = 2$。Aurora 吃掉接下来的两块，Bianca 吃掉最后一块。游戏结束时，Bianca 的总幸福度为 $3$。

第一次变更后，重量变为 $[1,1,20,1,2]$。

• 现在 Aurora 选择 $X=2$ 是最优的。（如果她选其他值，Bianca 会选择 $Y = 2$，那么 Aurora 就吃不到中间那块大饼干了。）响应 Aurora 的选择，Bianca 选择 $Y = 0$ 并吃掉第一块饼干。剩下的饼干重量为 $[1,20,1,2]$。
• 第二回合，Aurora 选择 $X = 1$，Bianca 选择 $Y = 0$。Bianca 再次吃掉最顶上的饼干。之后，剩下的饼干重量为 $[20,1,2]$。
• 第三回合，Aurora 选择 $X=0$。Bianca 选择 $Y = 2$。之后，Aurora 吃掉重量为 $20$ 和 $1$ 的饼干，最后 Bianca 吃掉最后一块重量为 $2$ 的饼干。Bianca 吃掉的饼干总重量为 $1+1+2 = 4$。

第二次变更后，重量变为 $[1,1,20,30,2]$。 如果两个女生都以最优策略进行游戏，Bianca 会吃掉除重量为 $30$ 的那块以外的所有饼干。

约束条件

• $2 \leq N \leq 100\ 000$。
• $0 \leq Q \leq 100\ 000$。
• $1 \leq W_i \leq 50$（是的，意大利杏仁饼干很轻！）。
• $0 \leq P_i \leq N-1$ 且 $1 \leq Z_i \leq 50$。

评分方式

你的程序将在分成若干子任务的测试数据上进行测试。 要获得某个子任务的分数，你必须正确解出该子任务中所有的测试数据。

• 子任务 0 [$0$ 分]: 样例。
• 子任务 1 [$8$ 分]: $Q = 0$ 且 $W_i = 1$。
• 子任务 2 [$9$ 分]: $N \le 3, Q \le 5$。
• 子任务 3 [$11$ 分]: 在任何时候，饼干重量 $W_i$ 都是非递增的；换句话说，$W_0 \ge W_1 \ge ... \ge W_{N-1}$。
• 子任务 4 [$13$ 分]: $N \le 100, Q \le 50$。
• 子任务 5 [$18$ 分]: $N \le 20\,000, Q \le 50$。
• 子任务 6 [$12$ 分]: $N \le 20\,000, Q \le 5000$。
• 子任务 7 [$29$ 分]: 没有额外的约束条件。