Migrated from Lutece 2923 百战天虫：重装上阵

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你正在玩一个战略游戏，你正在操纵一只可以使用各种武器的虫子。在这个问题里，你只能使用一种武器，它可以在百亿米高空处任意水平位置产生一个神驴雕像，从天而降。

神驴雕像在判定上可以视为一个圆柱体，底盘直径为 $d$ ，初始时有一定能量，若下落到底盘高度为某个 $h$ 时碰到墙体，可以清除底盘正下方墙体高度在 $h-1$ 到 $h$ 的部分，消耗一点能量，并继续竖直下落，直到能量为负数。若神驴雕像碰到虫子，只需一瞬间就可以消灭他们。

现在地面上有 $n$ 只敌方虫子排成一排，每只虫子与相邻虫子距离为 $1$ ，第 $i$ 只虫子上方有一个宽为 $0.5$ ，高度为 $a_i$ 的墙体，若现在到你出手使用武器，请问至少需要给神驴雕像充入多少点能量，才能让它击杀到敌方虫子？

虫子视为质点，没有宽度，而墙有宽度。

然而你觉得使用一次不够爽，所以你使用一次之后会将所有被毁墙体还原，并换另一个底盘直径可能不同的神驴雕像再玩一次。你想玩 $q$ 次，所以你需要回答 $q$ 次。

请注意，由于你想玩的次数太多，你可能需要使用更快的输入方式。

Input

第一行一个整数 $n$ ，表示虫子个数。

第二行 $n$ 个整数 $a_i$ ，第 $i$ 个数表示第 $i$ 只虫子上方墙体高度。

第三行一个整数 $q$ ，表示询问个数。

接下来 $q$ 行每行一个整数 $d$ ，表示当前询问下神驴雕像的底盘直径。

Output

输出 $q$ 行，第 $i$ 行一个整数表示第 $i$ 个询问的答案。

Samples

6
4 1 2 1 5 3
3
1
3
4

1
2
3

Constraints

$1 \le n \le 10^6 , 1 \le a_i \le 10^9 , 1 \le q \le 10^6 , 1 \le d \le n$

Note

请注意样例中最后一个询问，神驴雕像的放法是放在 $[n,n+3]$ 位置，也就是说神驴雕像可以超出 $1$ 和 $n$ 。

Resources

2023 UESTC ICPC Training for Data Structures