题目描述

在 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$ 开始的总旅行距离。

题目大意

题目描述

在 JOI 市里，有一条长度非常长的路，可以看做一个实数数轴。这条路上有 $N$ 个景点 $1,2,\dots,N$，它们按照坐标递增的顺序编号。第 $i$ 个景点位于坐标为 $X_i$ 处。

Bitaro 打算参观 JOI 市的所有景点。因为贪心是他人生的口号，所以他会按以下方式不断前往最近的未参观过的景点，直到参观完毕：

令 $x$ 表示 Bitaro 当前所在的位置。从尚未参观过的景点中选取距离 Bitaro 的当前位置最近的景点 $i$，使得 $|x-X_i|$ 的值最小。然后将 Bitaro 移动到第 $i$ 个景点并参观它。如果有多个最近的景点，则移动到它们中编号最小的那个。其中 $|t|$ 表示 $t$ 的绝对值。 但是，由于多年的经验，Bitaro 知道如果只按上述方式移动，那么他的总路程可能会比预想的更长。由于总路程和起始坐标有关，他想知道从 $Q$ 个起始坐标 $S_1,S_2,\dots,S_Q$ 出发，分别需要走多少路程才能参观完所有的景点。

为了帮助 Bitaro，你需要编写一个程序，给出在每个起始坐标处开始前往参观所有景点时所需走的总路程。

输出格式

共输出 $Q$ 行。对于每一行，输出从该起点开始走过所有景点后的总路程。

Translate by

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$，保证所有输入均为整数。

子任务编号	分值	限制
$1$	$5$	$Q=1, N \le 2 \times 10^3$
$2$	$10$	$Q=1$
$3$	$30$	$X_{i+1} - X_i \le 100$
$4$	$55$	无

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