题目描述

题目译自 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$ 出发，他游览完所有景点所经过的游览路线长度。

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\le N,Q\le 2\times 10^5$
• $0\le X_i,S_j\le 10^9,X_i<X_{i+1}$

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