题面描述

羽未和海己喜欢玩夏兜游戏。

现在有一个长度为 $n$ 的序列 $a_1, ...,a_n$。一开始，羽未在第一个位置，海己在第二个位置。羽未每在一个位置会把这个位置涂成红色，海己每在一个位置会把这个位置涂成蓝色。

每个回合，更靠左的选手移动。移动的时候，它可以跳到一个更右边的且尚未染色的位置，然后将那个位置染上色。

游戏结束后，羽未的分数为红色位置的 $a_i$ 总和，海己分数为蓝色位置的 $a_i$ 总和。两个人都为了最大的分数而采取最优策略，请你求出羽未的分数减去海己的分数的差。

为了增加趣味性，她们打算玩 $Q$ 轮游戏。每轮游戏仅改动 $a_n$。你需要求出 $Q$ 轮的所有答案。

输入格式

第一行一个正整数 $n$。

随后一行 $n-1$ 个非负数 $a_1,...,a_{n-1}$。

随后一个正整数 $Q$。

随后 $Q$ 行每行一个非负数，表示第 $Q$ 轮时的 $a_n$。

输出格式

输出 $Q$ 行，表示每轮的答案。

样例

样例输入 1

5
1 3 4 2
4
3
5
10
15

样例输出 2

1
-1
2
7

大样例

数据范围

对于所有数据，满足 $3\leq n \leq 2 \times 10^5$，$0 \leq a_{1,...,n-1} \leq 10^6$，$0 \leq a_n \leq 10^9$。