题目描述

题目译自 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$,$2$,$3$,$4$,$5$，这些景点距离 Bitaro 目前位置的距离分别为 $7$,$2$,$1$,$0$,$2$。因为景点 $4$ 离 Bitaro 目前位置最近，他会留在坐标 $7$ 位置并游览景点 $4$。

他还没游览的景点为 $1$,$2$,$3$,$5$，这些景点距离 Bitaro 目前位置的距离分别为 $7$,$2$,$1$,$2$。因为景点 $3$ 离 Bitaro 目前位置最近，他会从坐标 $7$ 前往坐标 $6$ 并游览景点 $3$。

他还没游览的景点为 $1$,$2$,$5$，这些景点距离 Bitaro 目前位置的距离分别为 $6$,$1$,$3$。因为景点 $2$ 离 Bitaro 目前位置最近，他会从坐标 $6$ 前往坐标 $5$ 并游览景点 $2$。

他还没游览的景点为 $1$,$5$，这些景点距离 Bitaro 目前位置的距离分别为 $5$,$4$。因为景点 $5$ 离 Bitaro 目前位置最近，他会从坐标 $5$ 前往坐标 $9$ 并游览景点 $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}$

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

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

要不要我帮你检查一下是否有遗漏的数学符号没添加 $？$ 或者需要调整某些符号的格式（比如把连续符号的 $合并$ 等），可以随时告诉我~