该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile3977.zip](file://AdditionalFile3977.zip?type=additional_file)

#3977. 「JOISC 2023 Day4」Bitaro 之旅

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOISC 2023 Day4 T3 「ビ太郎の旅 / Bitaro's Travel」

JOI 市有一条非常长的路，可以将其看成实数轴。路上的一个位置用一个实数坐标表示。在 JOI 市，沿路有 $N$ 个景点，按坐标递增顺序编号为 $1$ 到 $N$。第 $i\ (1\le i\le N)$ 个景点的坐标是 $X_i$。

Bitaro 会游览 JOI 市的所有景点。因为「贪心」是他的人生信条，他会重复如下操作直到他游览了所有景点：

• 令 $x$ 为 Bitaro 目前所在的位置。在他还没游览的景点中，他会选择离目前自己所在位置最近的景点 $i$，即 $|x-X_i|$ 最小的景点 $i$，然后移动到景点 $i$ 并游览。如果有多个景点满足条件，他会移向坐标最小的那个景点。这里 $|t|$ 表示 $t$ 的绝对值。

然而，由于多年来的经验，Bitaro 知道如果他只是重复上述过程，游览路线总长度可能会被他预期的长。因为游览路线总长度随起始坐标的变化而变化，他想知道如果他从 $Q$ 个候选起始坐标 $S_1,S_2,\ldots,S_Q$ 出发的话，他游览完所有景点所经过的游览路线长度分别是多少。

给定 JOI 市的信息和候选起始坐标，写一个程序计算对于 Bitaro 从每个起点出发时，他游览完所有景点所经过的游览路线长度是多少。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $X_1,X_2,\ldots,X_N$。

第三行一个整数 $Q$。

接下来 $Q$ 行，每行一个整数 $S_j$。

输出格式

输出 $Q$ 行，第 $j$ 行输出一个整数，表示 Bitaro 从坐标 $S_j$ 出发，他游览完所有景点所经过的游览路线长度。

样例 1

输入

5
0 5 6 7 9
1
7

输出

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

输出

9
10
11
12
13
14
15
16
17
9

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

数据范围与提示

对于所有输入数据，满足：

• $1\le N,Q\le 2\times 10^5$
• $0\le X_i,S_j\le 10^9,X_i<X_{i+1}$

详细子任务附加限制及分值如下表所示。