定义一个数组的划分操作为：将这个数组划分为若干组，每组的长度为 或者 ，若一个组长度为 ，如：{x}，则其贡献的价值为 ，若一个组的长度为 ，如 {x,y}则其贡献的价值为 。

定义一个数组的美值为：找到某种划分操作，使得这种划分操作贡献的价值最大。比如数组 {1,-1,2,3} ,可以将数组划分为 {1}{-1,2}{3} 三组，其价值为，可以发现该方式是使得贡献价值最大的划分方式，所以该数组的美值为 。

定义子数组为：数组的一个连续片段。非空子数组即为数组的一个非空连续片段。

定义一个数组的美丽值为：该数组的非空子数组中的最大美值。

比如数组{-2,-1,2,3}，其美值最大的非空子数组为{-1,2,3}，可以发现这是其价值最大的非空子数组。

laoya 有一个长度为 的 a 数组，现在有 次询问。每次询问为 ，表示将 a[pos] 变成 x，每次询问后求更改后的 a 数组的美丽值（修改是永久的）。注意：答案可能为负数。

第一行输入两个整数 ，
接下来一行个整数，代表数组
接下来  行每行输入两个整数 ，

输出  行，每行代表每次修改后数组的美丽值

4 1
1 -1 2 3
1 -2

11

第一次修改后数组为 {-2,-1,2,3}。
其中美丽值最大的子数组为区间  即 {-1,2,3}。

该子数组美值的划分方式为 {-1,2} {3}，
则该子数组美值为 ，所以输出 。