28003번 - Bitaro’s Travel 서브태스크다국어

문제

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ドル ≤ i ≤ 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ドル ≤ j ≤ Q$) of output should contain the total traveling distance if Bitaro starts from the coordinate $S_j$.

제한

• 1ドル ≤ N ≤ 200,000円$.
• 1ドル ≤ Q ≤ 200,000円$.
• 0ドル ≤ X_i ≤ 10^9$ (1ドル ≤ i ≤ N$).
• $X_i < X_{i+1}$ (1ドル ≤ i ≤ N - 1$).
• 0ドル ≤ S_j ≤ 10^9$ (1ドル ≤ j ≤ Q$).
• Given values are all integers.

서브태스크

힌트