JOI 市有一条很长的道路，可以看作是一条实数轴。道路上的位置由实数坐标表示。JOI 市沿路有 $N$ 个观光景点，按坐标升序编号为 $1$ 到 $N$。第 $i$ 个观光景点（$1 \le i \le N$）的坐标为 $X_i$。

Bitaro 将参观 JOI 市的所有观光景点。由于“贪心”是他的人生格言，他会重复执行以下步骤，直到参观完所有观光景点：

• 设 $x$ 为 Bitaro 当前的坐标。在尚未参观的观光景点中，选取一个观光景点 $i$，使得从 Bitaro 当前位置到该景点的距离 $|x - X_i|$ 最小。然后，Bitaro 移动到观光景点 $i$ 的位置并参观它。如果有多个这样的观光景点，他会移动到坐标较小的那个。这里 $|t|$ 表示 $t$ 的绝对值。

然而，凭借多年的经验，Bitaro 知道如果他通过重复上述步骤移动，总行程距离可能会比他预期的要长。由于总行程距离会根据起始坐标的不同而变化，他想知道如果他从 $Q$ 个起始坐标候选 $S_1, S_2, \dots, S_Q$ 中的每一个出发，直到参观完所有观光景点为止的总行程距离。

为了帮助 Bitaro，请编写一个程序，在给定 JOI 市的信息和起始坐标候选的情况下，计算他从每个起始坐标出发时的总行程距离。

输入格式

从标准输入读取以下数据：

$N$ $X_1 \ X_2 \ \dots \ X_N$ $Q$ $S_1$ $S_2$ $\vdots$ $S_Q$

输出格式

输出 $Q$ 行到标准输出。第 $j$ 行（$1 \le j \le Q$）应包含 Bitaro 从坐标 $S_j$ 出发时的总行程距离。

数据范围

• $1 \le N \le 200\,000$
• $1 \le Q \le 200\,000$
• $0 \le X_i \le 10^9$ ($1 \le i \le N$)
• $X_i < X_{i+1}$ ($1 \le i \le N - 1$)
• $0 \le S_j \le 10^9$ ($1 \le j \le Q$)
• 给定值均为整数。

子任务

1. (5 分) $Q = 1, N \le 2\,000$
2. (10 分) $Q = 1$
3. (30 分) $X_{i+1} - X_i \le 100$ ($1 \le i \le N - 1$)
4. (55 分) 无附加限制

样例

样例输入 1

5
0 5 6 7 9
1
7

样例输出 1

15

说明

如果 Bitaro 从坐标 $7$ 出发，他参观所有观光景点的过程如下：

1. 他尚未参观观光景点 $1, 2, 3, 4, 5$，距离 Bitaro 当前位置的距离分别为 $7, 2, 1, 0, 2$。由于观光景点 $4$ 是距离 Bitaro 最近的观光景点，他停留在坐标 $7$ 并参观观光景点 $4$。
2. 他尚未参观观光景点 $1, 2, 3, 5$，距离 Bitaro 当前位置的距离分别为 $7, 2, 1, 2$。由于观光景点 $3$ 是距离 Bitaro 最近的观光景点，他从坐标 $7$ 移动到坐标 $6$ 并参观观光景点 $3$。
3. 他尚未参观观光景点 $1, 2, 5$，距离 Bitaro 当前位置的距离分别为 $6, 1, 3$。由于观光景点 $2$ 是距离 Bitaro 最近的观光景点，他从坐标 $6$ 移动到坐标 $5$ 并参观观光景点 $2$。
4. 他尚未参观观光景点 $1, 5$，距离 Bitaro 当前位置的距离分别为 $5, 4$。由于观光景点 $5$ 是距离 Bitaro 最近的观光景点，他从坐标 $5$ 移动到坐标 $9$ 并参观观光景点 $5$。
5. 他尚未参观观光景点 $1$。由于观光景点 $1$ 是距离 Bitaro 最近的观光景点，他从坐标 $9$ 移动到坐标 $0$ 并参观观光景点 $1$。

由于 Bitaro 的总行程距离为 $15$，输出 $15$。

样例输入 2

10
1 2 3 4 5 6 7 8 9 10
10
1
2
3
4
5
6
7
8
9
10

样例输出 2

9
10
11
12
13
14
15
16
17
9