题目描述

小猫接管了一座新公园的管理工作。公园中心有一座大型圆形雕塑，周围摆放着$N$盆花。每盆花会被赋予一个整数（可能为负数）表示其吸引力值。如下图所示：

（花盆的位置被编号为$1$到$N$。对于任意$i$（$1 \leq i < N$），第$i$盆花和第$i+1$盆花是相邻的，此外第$1$盆花和第$N$盆花也是相邻的。）

董事会主席要求小猫为游客建造“一个弧形藤椅”供休息，藤椅旁边的花的吸引力值之和应尽可能大。需要注意的是，藤椅不能构成一个完整的圆，因此藤椅旁边的花数量可以是$1, 2, \ldots, N-1$，但不能是$N$。在上图的例子中，如果我们沿着红色虚线弧建造藤椅，吸引力值之和为$3 + (-2) + 1 + 2 = 4$，这是所有可能构造中最大的。

不幸的是，一些捣蛋猫总是给小猫制造麻烦，他们会更换某些花盆。小猫的情报部门已经捕获了所有$M$条捣蛋猫的行动指令。每条指令的形式为“$A$ $B$”，表示将第$A$盆花更换为吸引力值为$B$的新花盆。你需要在每条指令后报告新的“最大和”。

输入格式

输入包含一组测试数据。第一行输入一个整数$N$（$4 \leq N \leq 100000$）。

第二行包含$N$个整数，表示每盆花的初始吸引力值。第$i$个数表示第$i$盆花的吸引力值。

第三行输入一个整数$M$（$4 \leq M \leq 100000$），接下来的$M$行每行包含一条指令“$A$ $B$”，形式如上所述。

限制条件：所有吸引力值的范围在$[-1000, 1000]$之间。保证最大和始终为正整数。

输出格式

对于每条指令，输出一行，表示当前最优藤椅的最大吸引力值之和。

示例输入与输出

输入数据 1

5
3 -2 1 2 -5
4
2 -2
5 -5
2 -4
5 -1

输出数据 1

4
4
3
5

来源

POJ Monthly--2006.01.22, Zeyuan Zhu