← 返回题目列表

AtCoder · codefestival_2016_final_h

H. 东海道

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

分数: 1600 点

问题陈述

有 N 连续的方块,已编号 1 通过 N 从左到右。 Snuke 和 Rng 正在使用这些方块玩棋盘游戏,如下所述:

  1. 首先,Snuke 将一个整数写入每个方格。
  2. 两名玩家各拥有一件棋子。 Snuke 将他的棋子放在方块上 1,Rng 将他的放到方块上 2.
  3. 棋子位于对手左边的玩家移动他的棋子。目的地必须是当前放置棋子的方格右侧的方格,并且不能是对手放置棋子的方格。
  4. 重复步骤 3. 当棋子无法再移动时,游戏结束。
  5. 每个玩家的得分计算为玩家在游戏结束前放置棋子的方格中写入的整数之和。

Snuke 已经写入了一个整数 A_i 成正方形 i (1≦i≦N-1),但不是方形 N 还没有。 他决定计算每一个 M 整数 X_1,X_2,...,X_M,如果他将其写入正方形 N 游戏开始后,“(Snuke 的分数) - (Rng 的分数)”值将是多少。 这里,假设每个玩家移动他的棋子以使值“(玩家的分数)-(对手的分数)”最大化。

约束

  • 3≦N≦200,000
  • 0≦A_i≦10^6
  • 所有的总和 A_i 最多是 10^6.
  • 1≦M≦200,000
  • 0≦X_i≦10^9

部分分数 通过满足以下条件的测试集将获得

  • 700 积分 M=1.
  • 附加 在没有额外限制的情况下通过测试集将获得 900 分数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 ... A_{N-1}
M
X_1
X_2
:
X_M

输出

对于每个 M 整数 X_1, ..., X_M,如果写入方块,则打印值“(Snuke's Score) - (Rng's Score)” N,每行一个。


示例输入 1

5
2 7 1 8
1
2

示例输出 1

0

游戏进行如下,其中 S 代表 Snuke 的作品,并且 R 代表 Rng 的。

两名玩家得分 10,因此“(Snuke 的分数) - (Rng 的分数)”是 0.


示例输入 2

9
2 0 1 6 1 1 2 6
5
2016
1
1
2
6

示例输出 2

2001
6
6
7
7