問題文
Niwango-kun 和 Nikomova-chan 正在玩硬币游戏。
简介 N 硬币 1 排成一排,从左到右 它的编号为 1 它们的编号最大为 N 。奇数硬币正面朝上,偶数硬币背面朝上。硬币 i 的值为 S_i 。
这个游戏是 N-1 游戏由回合组成,奇数回合的玩家是 Niwango-kun,偶数回合的玩家是 Nikomova-chan。i 在回合中,玩家收到硬币。 i 或硬币 您可以翻转其中一个 i+1 。如果你也不想翻转,那你也不必翻转。
N-1 回合结束后,Niwango 得到正面朝上的硬币,Nikomova 得到正面朝上的硬币。此时,你所获得的金币的价值总和就是你的分数。这个时候,Niwango的成绩会是多少呢?然而,2 由于人们非常聪明,每个人都会采取最佳策略来最大化他或她的分数。
另外,在开始游戏之前,Nikomova-chan 可能会在硬币上涂鸦,这可能会降低硬币的价值。 Nikomova-chan 完全 Q 涂鸦两次,i 我第一次乱涂乱画的硬币是一枚硬币 P_i 涂鸦硬币 i 的值为 D_i 它下降了。
Q 对于每个涂鸦,如果 Niwango 在涂鸦后立即开始游戏,则计算他的得分。
入力
输入将以以下格式从标准输入提供。
N S_1 S_2 ... S_N Q P_1 D_1 P_2 D_2 : P_Q D_Q
- 1 行代表硬币数量。 1 整数 N (2 ≦ N ≦ 200,000) 。 来自行
- 2 线代表硬币的初始值。 N 整数由空格分隔。其中 i 第一个整数 S_i (1 ≦ S_i ≦ 10^9) 是一枚硬币 表示 i 的初始值。
- 3 Nikomova-chan 涂鸦的次数显示在第一行。 1 整数 Q (0 ≦ Q ≦ 200,000) 。 来自行
- 4 从线 Q 行提供了有关 Nikomova-chan 涂鸦的信息。其中 i 第几行包含,2 整数 P_i (1 ≦ P_i ≦ N), D_i (1 ≦ D_i) 用空格分隔。这是i 第二个涂鸦的硬币 P_i 值得 D_i 表示该值已减少。然而,每枚硬币的价值始终是 保证 1 或更高。
部分点
针对此问题设置了部分分数。
- Q = 0 的数据集 如果您正确回答 1 , 给出10 点。 如果您正确回答
- S_i ≦ 25 的数据集 如果您正确回答 2 的回答正确,除上述之外, 80 点。 如果您正确回答
- 如果所有测试用例都回答正确,除了上述之外 90 点。 如果您正确回答
出力
输出是 第 Q+1 行组成。1 行输出从初始状态开始游戏时Niwango的得分,2 从行 Q+1 至行 i (1 ≦ i ≦ Q) 第几行包含,i 如果 Niwango 在第一个涂鸦后立即开始游戏,则输出 Niwango 的得分。还在输出末尾添加换行符。
入力例1
4 1 2 3 4 1 4 3
出力例1
7 5
在此示例中, 有4 个硬币,其面值从左到右排列。 1,2,3,4 。最初,硬币的顶面是两侧。如果从这个状态开始游戏,
- 二王后君硬币 翻开 2 → Nikomova-chan获得硬币 翻开 3 →Niwango获得硬币 翻转 4 翻
,而最终状态下硬币的顶面是“正面和背面”,所以 Niwango 的得分是 7 点。
另外,在这个例子中 有 1 查询。通过查询硬币 它下降到 4 值得 1 。如果从这个状态开始游戏,
- 二王后君硬币 翻开 2 → Nikomova-chan获得硬币 翻开 2 →Niwango获得硬币 翻转 4 翻
,而最终状态下硬币的顶面是“正面和背面”,所以 Niwango 的得分是 5 点。
入力例2
8 3 1 4 1 5 9 2 6 5 3 3 6 6 8 4 1 1 6 2
出力例2
19 16 16 12 11 11