← 返回题目列表

AtCoder · codefestival_2015_final_j

J. N个桶

中文机器翻译题面 查看原题

問題文

高桥将参加一个名为“桶节”的锦标赛。在水桶节上,会举行各种使用水桶的比赛,但对自己的能力充满信心的高桥说: 我决定参加一个名为N Buckets 的比赛。 “

「N 桶”的规则如下:

  • N 人 1 以团队形式参与。对于团队成员 指定一个编号 1~N 。
  • 团队成员 N 人们按照数字顺序顺时针围绕圆圈站立。 会员编号为i (1 ≦ i ≦ N-1) 与号码会员 i+1 成员, 编号为N 与号码会员 1 的成员将彼此相邻。
  • 相邻 2 成员之间共有水 N 桶已放置。团队可以讨论并决定在哪个桶中放入多少水。但是,所有水量都必须是整数值。
  • 你们双方的团队成员 2 举起两个桶。每个桶都是 2 小组成员将共同努力将其抬起。 如果你能举起所有N 桶,你就成功了,桶里的水总量就是你的分数。

高桥正在考虑他应该在哪个桶中放入多少水才能获得尽可能高的分数。为此,我们首先衡量了团队成员的优势。并且,i (1 ≦ i ≦ N) 会员的力量 事实证明 S_i 。功率是 p 的成员是 2 两桶水的平均量是 p 如果铲斗位于下方,您可以将其抬起。换句话说,2 每个桶中的水量为 w,v 然后,(w+v)/2 ≦ p 可以解除。

高桥的团队是一个临时团队,因此团队成员可能会发生变化。成员变动总数 Q 次,i (1 ≦ i ≦ Q) 在第二次更改中 编号 P_i 成员已更改,权力增加。 一位新成员是 X_i 我将以会员号 P_i 的身份加入。对于每次成员​​变化,求高桥队在变化后可以获得的最高分数。


入力

输入将以以下形式从标准输入给出。

N
S_1 S_2 ... S_N
Q
P_1 X_1
P_2 X_2
:
P_Q X_Q
  • 1 行包含一个表示参与者数量的整数。 N (3 ≦ N ≦ 10^5) 被给予。 100 在点数据集中,N 保证为偶数。
  • 2 线代表第一个团队成员的实力。 N 整数由空格分隔。其中 i (1 ≦ i ≦ N) 第一个整数 S_i (0 ≦ S_i ≦ 10^4) 是 对于i 会员的力量 事实证明 S_i 。
  • 3 行包含一个整数,表示团队成员变更的数量。 Q (1 ≦ Q ≦ 10^5) 被给予。
  • 4 从线 Q 行提供有关团队成员变更的信息。其中 给出了 i (1 ≦ i ≦ Q) 行中,2 整数 P_i (1 ≦ P_i ≦ N), X_i (0 ≦ X_i ≦ 10^4) 。这是i 随着第二次成员变更 表示将添加 P_i 成员已更改,权力增加。 一位新成员是 X_i 的新成员。

追加点

已针对此问题设置了附加点。 如果

  • N 对于奇数数据集也是正确的,那么1 将获得额外积分。

此外,不需额外加分 100 即使答案对于点数据集是正确的,此问题也会被视为正确答案。

出力

输出是 由 Q 行组成。其中 i (1 ≦ i ≦ Q) 行中,i 代表高桥队在第一次成员更换后立即可以获得的最高分数。 打印 1 整数。还在输出末尾添加换行符。


入力例1

4
2 2 2 2
2
1 3
3 0

出力例1

8
6

下图显示了每次更换成员后应将多少水放入哪个桶中才能立即获得最高分。圆圈代表成员,圆圈内的数字代表成员的实力,圆圈左上角的数字代表成员的编号。水桶图片内写的数字代表水桶中可放入的水量。

figure1

入力例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