问题描述

高桥君想要参加名为"Bucket Festival"的比赛。在Bucket Festival中，有许多使用水桶进行的竞技项目。高桥君自信满满，决定参加名为"$N$个水桶"的竞技项目。

"$N$个水桶"的规则如下：

• 参赛者分为一个由$N$人组成的团队。每个团队成员都被分配了从1到$N$的编号。
• 团队的$N$个成员按照顺时针的方向站在一个圆周上，编号从小到大。第$i (1 ≤ i ≤ N-1)$个成员和第$i+1$个成员，以及第$N$个成员和第$1$个成员是相邻的。
• 每两个相邻的成员之间放置$N$个装满水的水桶。关于每个水桶应该放多少水，团队可以商量决定。但是，水的量必须都是整数。
• 每个团队成员举起身边的两个水桶。这两个水桶需要由两个成员一同合作举起。如果能够举起所有的$N$个水桶，则表示成功，且所有水桶中的水的总量将成为得分。

为了获得尽可能高的得分，高桥君正在考虑应该将多少水放入哪些水桶中。他首先测量了团队成员的力量。经过测量，他得知第$i (1 ≤ i ≤ N)$个成员的力量为$S_i$。力量为$p$的成员可以举起他所拿的两个水桶，前提是这两个水桶中水的平均量不超过$p$。也就是说，如果两个水桶中的水量分别为$w$和$v$，那么只要$(w+v)/2 ≤ p$，他就可以举起这两个水桶。

由于高桥君的团队是一个临时团队，团队成员可能会发生变化。共进行了$Q$次成员变更，第$i (1 ≤ i ≤ Q)$次变更中，第$P_i$个成员发生了变更，新的成员加入，力量为$X_i$。请对每次成员变更后，计算出高桥君团队在该时刻能够获得的最高分数。

输入

从标准输入读取输入数据。

输入的格式如下：

$N$

$S_1$ $S_2$ ... $S_N$

$Q$

$P_1$ $X_1$

$P_2$ $X_2$

...

$P_Q$ $X_Q$

• 第一行包含一个整数$N (3 ≤ N ≤ 10^5)$，表示参赛者的人数。对于100个测试数据集，保证$N$是偶数。
• 第二行包含$N$个整数，以空格分隔，表示团队成员的初始力量。其中，第$i (1 ≤ i ≤ N)$个整数$S_i (0 ≤ S_i ≤ 10^4)$表示第$i$个成员的力量。
• 第三行包含一个整数$Q (1 ≤ Q ≤ 10^5)$，表示团队成员的变更次数。
• 接下来的$Q$行，每行包含两个整数$P_i (1 ≤ P_i ≤ N)$和$X_i (0 ≤ X_i ≤ 10^4)$，表示第$i$次成员变更中，第$P_i$个成员被替换为力量为$X_i$的新成员。

输出

输出共有$Q$行。其中，第$i (1 ≤ i ≤ Q)$行表示第$i$次成员变更后，高桥君团队在该时刻能够获得的最高分数，输出一个整数。最后一行末尾包含换行符。

示例1

4
2 2 2 2
2
1 3
3 0

输出示例1

8
6

下图展示了每次成员变更后，为获得最高分数，水桶中应该放置多少水的分配方案。圆圈代表团队成员，圆圈中的数字代表成员的力量，左上角的数字代表成员的编号。水桶示意图中的数字表示水桶中装满水的量。

示例2

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

输出示例2

0
20000
20000
20000
40000
60000