题目描述

译自 ROIR 2020 Day2 T4. Плакаты,译者ksyx

你的朋友们为了会见 IOI 回来的国家队选手准备了很多漂亮的海报，现在就还差要考虑些细节了。

为了欢迎这些选手，你的 $n$ 个朋友会拿着海报站成一个圈。为了方便描述，我们把他们编号为朋友 $1\ldots n$，其中对于 $i\in [1,n-1]$，朋友 $i$ 和朋友 $i+1$ 站在一起，且朋友 $n$ 和朋友 $1$ 站在一起。

每张海报都有一个美观度，其中朋友 $i$ 拿着的海报的美观度为 $a_i$。当开始庆祝时，一些朋友会举起他们的海报。为了美观，不能有 $4$ 个或以上排在一起的朋友同时举起他们的海报。

为了能够丰富节目效果，你的朋友们还打算在庆祝过程中更换 $q$ 次海报。每次更换后，海报 $p_i$ 的美观度将变为 $q_i$。你的朋友想知道每次更换后在符合上述条件下的最大美观度之和。

你的任务是给出初始的美观度，求出初始以及各次更换后的最大美观度之和。

译者注：题面省略了部分难以理解的不必要细节。

输入格式

第一行一个整数 $n$，朋友总数。

接下来一行 $n$ 个整数 $a_i$，表示初始美观度。

第三行 $q$ 个整数表示海报更换次数。

接下来 $q$ 行每行两个整数 $p_i,~v_i$，描述一次更换。

输出格式

输出 $q+1$ 行，表示初始时及各次更换后最大的美观度之和。

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

17
13
15

提示

【样例 1 解释】

初始状态下最佳方案为让朋友 $2,~4,~5,~6$ 举起海报，此时美观度之和为 $17$。

第一次改变后朋友 $6$ 的海报美观度变为 $0$，在此情况下最佳方案为让朋友 $1,~3,~4,~5$ 举起海报，美观度之和为 $13$。

第二次改变后朋友 $2$ 的海报美观度变为 $5$，在此情况下最佳方案为让朋友 $1,~2,~4,~5$ 举起海报，美观度之和为 $15$。

【数据范围】

对于 $100\%$ 的数据，有 $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$

各子任务如下：