题目描述

题目译自 Ukrainian Olympiads in Informatics 2016 Stage 4 Day1 T4. Пограбування

在奥林匹亚国，银行系统非常发达，因此居民们很乐意将储蓄存入银行。总共有 $N$ 家银行，排成一排。第 $i$ 家银行存有 $a_i$ 图格里克。最初，这些银行没有能够阻止抢劫的安全系统。然而，众所周知，如果在第 $d$ 天晚上第 $b$ 家银行被抢劫，那么在第二天早上，其相邻的银行（$b-1$ 和 $b+1$）将安装必要的安全系统，此后这些银行就无法再被抢劫。在第 $d+i$ $(i>0)$ 天的早上，安全系统将被安装在第 $b-i$ 和 $b+i$ 家银行。这个过程将持续下去，直到所有银行都被保护起来免受抢劫。被抢劫过的银行永远不能再次被抢劫。

不幸的是，在奥林匹亚，就连罪犯也热衷于解决奥林匹克竞赛题，因此政府毫不怀疑，如果有人策划一系列抢劫，他们会以最优的方式进行，换句话说，他们会最大化在银行安装安全系统之前能成功抢劫到的图格里克总数。此外，还知道罪犯每天抢劫不超过一家银行，并且他们只在晚上作案。

银行系统在分析抢劫可能造成的损失时，会依次考虑 $M+1$ 种资金分布方案。每一种方案都与前一种方案在其中一家银行的存款金额上有所不同。

请编写一个名为 robbery 的程序，对于每一种资金分布方案，计算出因抢劫可能造成的最大损失。

输入格式

输入文件的第一行包含数字 $N$ 和 $M$，分别是银行的数量和图格里克数量变更操作的次数。

下一行包含 $N$ 个数字 $a_i$，表示各银行的初始图格里克数量。

接下来是 $M$ 行，每行包含一对数字 $B$ 和 $T$，表示在又一次操作后，第 $B$ 家银行的图格里克数量将变为 $T$。

输出格式

对于每个 $i$ $(0 \leq i \leq M)$，在单独的一行中向输出文件输出罪犯在完成 $i$ 次操作后能偷走的最大图格里克数量。

7 4
6 7 5 6 2 2 4
6 5
7 2
7 6
4 6

17
18
18
19
19

在接下来的示意图中，$0$ 表示被抢劫的银行，$-1$ 表示已安装安全系统的银行。

对于初始的资金分布方案，抢劫犯的行动如下：

• $[6,7,5,6,2,2,4]$ — 初始状态；
• $[6,7,5,0,2,2,4]$ — 抢劫了第四家银行（$6$ 图格里克）；
• $[6,7,-1,0,-1,2,4]$ — 第二天早上，在相邻的银行安装了安全系统；
• $[6,0,-1,0,-1,2,4]$ — 抢劫了第二家银行（$7$ 图格里克）；
• $[-1,0,-1,0,-1,-1,4]$ — 安全系统被安装在第一家银行（因为第二家被抢）和第六家银行（因为第四家在两天前被抢）；
• $[-1,0,-1,0,-1,-1,0]$ — 抢劫了最后一家银行（$4$ 图格里克）。 总计，抢劫犯获得了 $17$ 图格里克。

最后的资金分布方案将是：$[6,7,5,6,2,5,6]$。总计，抢劫犯可以获得 $6 + 7 + 6 = 19$ 图格里克，如果他们按顺序抢劫第四家、第二家，然后是第七家银行。

数据范围与提示

详细子任务附加限制及分值如下表所示：