题目背景

翻译自 CSES-1190 题。

题目描述

给定一个包含 $n$ 个整数的数组。数组中的一些值将被更新，每次更新后，您的任务是报告数组中的最大子数组和。

本题中子数组定义为：任意给定一个数组下标 $l,r(1\le l\le r\le n)$，得到的区间 $[l,r]$ 中的数组元素 $a_{l},a_{l+1},\cdots,a_r$。即可以理解成连续子序列。

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示数组的大小和更新的次数。数组的索引从 $1$ 到 $n$。

第二行包含 $n$ 个整数 $x_1,x_2,\ldots,x_n$：表示数组的初始内容。

接下来有 $m$ 行描述更新操作。每一行包含两个整数 $k$ 和 $x$：表示将数组中位置 $k$ 的值更新为 $x$。

输出格式

对于每次更新操作，输出更新后的数组的最大子数组和。空子数组（和为 $0$）是允许的。

样例

5 3
1 2 -3 5 -1
2 6
3 1
2 -2

9
13
6

数据范围

• $1 \le n,m \le 2 \cdot 10^5$
• $-10^9 \le x_i \le 10^9$
• $-10^9 \le x \le 10^9$
• $1 \le k \le n$