P9342 [JOIST 2023] 比太郎之旅 / Bitaro's Travel

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

**【样例解释 #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 提供。