U537434 巴巴博弈

本题不卡常，写出普通的区间 dp 即可通过。

小 A 和小 B 要用一个数列进行博弈。他们轮流操作，每次操作可以选择取走数列最左边或最右边的元素。一个人的得分被定义为他取走的所有数的和，他们的目标都是让得分尽可能大。 小 A 先手，他想知道在两人都采取最优策略的情况下，他能得到多少分。 但这个数列会变化 $q$ 次，第 $i$ 次变化中给出 $x$，则 $a_i \leftarrow x$。小 A 要你在每次变化后告诉他答案。

第一行两个正整数 $n,q$，表示数列初始的长度和变化的次数。 第二行 $n$ 个正整数 $a_1 \sim a_n$，表示初始的数列。 接下来 $q$ 行，第 $i$ 行的正整数 $x$ 表示第 $i$ 次变化后 $a_i$ 的值。

对于每次变化，输出一行一个整数表示答案。

### 样例解释 第一次修改后，序列变为 $\{1,1,1,2,1\}$，可以证明小 A 无法拿到这个 $2$。 第二次修改后，序列变为 $\{1,2,1,2,1\}$。悲催地，小 A 仍然无法拿到任何一个 $2$。 第三次修改后，序列变为 $\{1,2,9,2,1\}$。 小 A 肯定要先取走一个 $1$，此时如果小 B 取走另一个 $1$，则小 A 只能取走一个 $2$，小 B 取走 $9$，小 A 取走剩下的一个 $2$。 ### 数据范围 | 测试点编号 | $n \le$ | 特殊性质 | |:-:|:-:|:-:| | $1 \sim 2$ | $10$ | 无 | | $3$ | $100$ | 无 | | $4$ | $10^3$ | A | | $5 \sim 6$ | $10^3$ | $q=1$ | | $7 \sim 10$ | $10^3$ | 无 | 特殊性质 A：保证 $a$ 始终单调不降。 对于 $100\%$ 的数据，$1 \le q \le n \le 10^3$，$1 \le a_i , x \le 2 \times 10^9$。