题目描述

在 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\cdots X_N$

$Q$

$S_1$

$S_2$

$\vdots$

$S_Q$

输出格式

向标准输出写入 $Q$ 行。输出的第 $j$ 行 $(1 \le j \le Q)$ 应包含如果 Bitaro 从坐标 $S_j$ 开始的总旅行距离。

5
0 5 6 7 9
1
7

15

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

9
10
11
12
13
14
15
16
17
9

提示

【样例解释 #1】

如果 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】

该样例满足子任务 $3, 4$ 的限制。

【数据范围】

对于所有测试数据，满足 $1 \le N, Q \le 2 \times 10^5$，$0 \le X_i \le 10^9$，$X_i < X_{i+1}$，$0 \le S_j \le 10^9$，保证所有输入均为整数。

题面翻译由 ChatGPT-4o 提供。