P9790 [ROIR 2020] 海报 (Day 2)

**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day2 T4.** ***[Плакаты](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day2.pdf)***,译者ksyx 你的朋友们为了会见 IOI 回来的国家队选手准备了很多漂亮的海报，现在就还差要考虑些细节了。 为了欢迎这些选手，你的 $n$ 个朋友会拿着海报站成一个圈。为了方便描述，我们把他们编号为朋友 $1\ldots n$，其中对于 $i\in [1,n-1]$，朋友 $i$ 和朋友 $i+1$ 站在一起，且朋友 $n$ 和朋友 $1$ 站在一起。 每张海报都有一个美观度，其中朋友 $i$ 拿着的海报的美观度为 $a_i$。当开始庆祝时，一些朋友会举起他们的海报。为了美观，不能有 $4$ 个或以上排在一起的朋友同时举起他们的海报。 为了能够丰富节目效果，你的朋友们还打算在庆祝过程中更换 $q$ 次海报。每次更换后，海报 $p_i$ 的美观度将变为 $v_i$。你的朋友想知道每次更换后在符合上述条件下的最大美观度之和。 你的任务是给出初始的美观度，求出初始以及各次更换后的最大美观度之和。 *译者注：题面省略了部分难以理解的不必要细节。*

第一行一个整数 $n$，朋友总数。 接下来一行 $n$ 个整数 $a_i$，表示初始美观度。 第三行 $q$ 个整数表示海报更换次数。 接下来 $q$ 行每行两个整数 $p_i,~v_i$，描述一次更换。

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

#### 【样例 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$。 各子任务如下： |子任务编号|分值|限制| |:-:|:-:|:-:| |$1$|$11$|$4 \le n \le 10,~q=0$| |$2$|$12$|$4 \le n \le 10,~0\le q\le 10$| |$3$|$13$|$4 \le n \le 1000,~0\le q\le 1000$| |$4$|$17$|$4 \le n \le 40000,~q=0$| |$5$|$47$|$4 \le n \le 40000, 0\le q\le 40000$|