{"raw_statement":[{"iden":"statement","content":"**译自 [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\n\n你的朋友们为了会见 IOI 回来的国家队选手准备了很多漂亮的海报，现在就还差要考虑些细节了。\n\n为了欢迎这些选手，你的 $n$ 个朋友会拿着海报站成一个圈。为了方便描述，我们把他们编号为朋友 $1\\ldots n$，其中对于 $i\\in [1,n-1]$，朋友 $i$ 和朋友 $i+1$ 站在一起，且朋友 $n$ 和朋友 $1$ 站在一起。\n\n每张海报都有一个美观度，其中朋友 $i$ 拿着的海报的美观度为 $a_i$。当开始庆祝时，一些朋友会举起他们的海报。为了美观，不能有 $4$ 个或以上排在一起的朋友同时举起他们的海报。\n\n为了能够丰富节目效果，你的朋友们还打算在庆祝过程中更换 $q$ 次海报。每次更换后，海报 $p_i$ 的美观度将变为 $v_i$。你的朋友想知道每次更换后在符合上述条件下的最大美观度之和。\n\n你的任务是给出初始的美观度，求出初始以及各次更换后的最大美观度之和。\n\n*译者注：题面省略了部分难以理解的不必要细节。*"},{"iden":"input","content":"第一行一个整数 $n$，朋友总数。\n\n接下来一行 $n$ 个整数 $a_i$，表示初始美观度。\n\n第三行 $q$ 个整数表示海报更换次数。\n\n接下来 $q$ 行每行两个整数 $p_i,~v_i$，描述一次更换。"},{"iden":"output","content":"输出 $q+1$ 行，表示初始时及各次更换后最大的美观度之和。"},{"iden":"note","content":"#### 【样例 1 解释】\n初始状态下最佳方案为让朋友 $2,~4,~5,~6$ 举起海报，此时美观度之和为 $17$。\n\n第一次改变后朋友 $6$ 的海报美观度变为 $0$，在此情况下最佳方案为让朋友 $1,~3,~4,~5$ 举起海报，美观度之和为 $13$。\n\n第二次改变后朋友 $2$ 的海报美观度变为 $5$，在此情况下最佳方案为让朋友 $1,~2,~4,~5$ 举起海报，美观度之和为 $15$。\n\n#### 【数据范围】\n对于 $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$。\n\n\n各子任务如下：\n\n|子任务编号|分值|限制|\n|:-:|:-:|:-:|\n|$1$|$11$|$4 \\le n \\le 10,~q=0$|\n|$2$|$12$|$4 \\le n \\le 10,~0\\le q\\le 10$|\n|$3$|$13$|$4 \\le n \\le 1000,~0\\le q\\le 1000$|\n|$4$|$17$|$4 \\le n \\le 40000,~q=0$|\n|$5$|$47$|$4 \\le n \\le 40000, 0\\le q\\le 40000$|"}],"translated_statement":null,"sample_group":[["6\n1 2 3 4 5 6\n2\n6 0\n2 5","17\n13\n15"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}