题目描述

There is a very long road in JOI City, which can be considered as the real number line. A position on the road is represented by a real number coordinate. In JOI City, there are $N$ sightseeing spots along the road, numbered from $1$ to $N$ in ascending order of the coordinates. The coordinate of the $i$-th sightseeing spot $(1\le i\le N)$ is $X_i$.

Bitaro will visit all the sightseeing spots in JOI City. Since "greedy" is the slogan of his life, he will repeat the following procedures until he visits all the sightseeing spots.

• Let $x$ be Bitaro’s current coordinate. Among the sightseeing spots he has not yet visited, take the sightseeing spot $i$ where the distance $|x − X_i|$ from Bitaro's current position takes a minimum value. Then Bitaro moves to the position of the sightseeing spot $i$, and visits it. If there are more than one such sightseeing spots, he moves to the sightseeing spot whose coordinate is smaller than the others. Here, $|t|$ is the absolute value of $t$.

However, thanks to long years of experience, Bitaro knows that if he moves by repeating the above procedures, the total traveling distance may be longer than he expected. Since the total traveling distance varies according to the starting coordinate, he wants to know the total traveling distance until he visits all the sightseeing spots if he starts from each of $Q$ candidates of starting coordinates $S_1, S_2,\dots, S_Q$.

To help Bitaro, write a program which calculates the total traveling distance if he starts from each of the candidates of starting coordinates, given information of JOI City and candidates of starting coordinates.

输入格式

Read the following data from the standard input.

$N$

$X_1\ X_2\cdots X_N$

$Q$

$S_1$

$S_2$

$\vdots$

$S_Q$

输出格式

Write $Q$ lines to the standard output. The $j$-th line $(1 \le j \le Q)$ of output should contain the total traveling distance if Bitaro starts from the coordinate $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】

If Bitaro starts from the coordinate $7$, he visits all the sightseeing spots as follows.

1. He has not yet visited the sightseeing spots $1, 2, 3, 4, 5$, and the distances from Bitaro’s current position are $7, 2, 1, 0, 2$, respectively. Since the sightseeing spot $4$ is the nearest sightseeing spot from Bitaro, he stays at the coordinate $7$ and visits the sightseeing spot $4$.
2. He has not yet visited the sightseeing spots $1, 2, 3, 5$, and the distances from Bitaro’s current position are $7, 2, 1, 2$, respectively. Since the sightseeing spot $3$ is the nearest sightseeing spot from Bitaro, he moves from the coordinate $7$ to the coordinate $6$ and visits the sightseeing spot $3$.
3. He has not yet visited the sightseeing spots $1, 2, 5$, and the distances from Bitaro’s current position are $6, 1, 3$, respectively. Since the sightseeing spot $2$ is the nearest sightseeing spot from Bitaro, he moves from the coordinate $6$ to the coordinate $5$ and visits the sightseeing spot $2$.
4. He has not yet visited the sightseeing spots $1, 5$, and the distances from Bitaro’s current position are $5, 4$, respectively. Since the sightseeing spot $5$ is the nearest sightseeing spot from Bitaro, he moves from the coordinate $5$ to the coordinate $9$ and visits the sightseeing spot $5$.
5. He has not yet visited the sightseeing spot $1$. Since the sightseeing spot $1$ is the nearest sightseeing spot from Bitaro, he moves from the coordinate $9$ to the coordinate $0$ and visits the sightseeing spot $1$.

Since Bitaro’s total traveling distance is $15$, output $15$.

该样例满足所有子任务的限制。

【样例解释 #2】

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

【数据范围】

对于所有测试数据，满足 $1\le N,Q\le2\times10^5$，$0\le X_i\le10^9$，$X_i<X_{i+1}$，$0\le S_j\le10^9$，保证所有输入均为整数。

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