好的，我们重新整理题目描述，并在公式和数字前后加上 $ 符号。

题目描述

你的 $n$ 个朋友为了欢迎 IOI 选手，准备举海报站成一个 圈。
为了方便，将他们编号为 $1 \ldots n$，其中对于 $i \in [1, n-1]$，朋友 $i$ 和朋友 $i+1$ 相邻，且朋友 $n$ 和朋友 $1$ 相邻。

每个朋友 $i$ 的海报有一个美观度 $a_i$。
庆祝时，一些朋友会举起海报，但 不允许有连续 $4$ 个或以上朋友同时举起海报。

此外，在庆祝过程中会有 $q$ 次更换海报的操作：
第 $j$ 次更换会将朋友 $p_j$ 的海报美观度改为 $v_j$。

你的任务是：

• 输出初始时在限制条件下的 最大美观度之和；
• 然后输出每次更换后的 最大美观度之和。

输入格式

第一行一个整数 $n$，朋友总数。
第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示初始美观度。
第三行一个整数 $q$，海报更换次数。
接下来 $q$ 行，每行两个整数 $p_i, v_i$，表示一次更换。

输出格式

输出 $q+1$ 行：

• 第 $1$ 行：初始时的最大美观度之和；
• 第 $2$ 至 $q+1$ 行：每次更换后的最大美观度之和。

样例

输入

6
1 2 3 4 5 6
2
6 0
2 5

输出

17
13
15

解释：

• 初始时最佳方案：朋友 $2, 4, 5, 6$ 举起海报，美观度和为 $1+2+3+4+5+6$ 中选部分，实际是 $2+4+5+6=17$。
• 第一次更换后：朋友 $6$ 的海报美观度变为 $0$，最佳方案：朋友 $1, 3, 4, 5$ 举起海报，美观度和为 $1+3+4+5=13$。
• 第二次更换后：朋友 $2$ 的海报美观度变为 $5$，最佳方案：朋友 $1, 2, 4, 5$ 举起海报，美观度和为 $1+5+4+5=15$。

数据范围

• $4 \le n \le 40000$
• $0 \le a_i, v_i \le 10^9$
• $1 \le p_i \le n$
• $0 \le q \le 40000$