L - ビ太郎の旅 (Bitaro's Travel) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

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, \ldots, 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.


Input

Read the following data from the standard input.

N
X_1 X_2 \cdots X_N
Q
S_1
S_2
\vdots
S_Q

Output

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.

Constraints

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

Subtasks

  1. (5 points) Q = 1, N \le 2\,000.
  2. (10 points) Q = 1.
  3. (30 points) X_{i+1} - X_i \le 100 (1 \le i \le N - 1).
  4. (55 points) No additional constraints.

Sample Input 1

5
0 5 6 7 9
1
7

Sample Output 1

15

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.

This sample input satisfies the constraints of all the subtasks.


Sample Input 2

10
1 2 3 4 5 6 7 8 9 10
10
1
2
3
4
5
6
7
8
9
10

Sample Output 2

9
10
11
12
13
14
15
16
17
9

This sample input satisfies the constraints of Subtasks 3, 4.

配点 : 100 点

問題文

JOI 市には 1 本の十分に長い道路がある.この道路は数直線とみなすことができ,各地点は 1 個の実数による座標で表される.また,JOI 市にはこの道路に沿って N 箇所の観光地があり,座標の小さい順に 1 から N までの番号が付けられている.観光地 i (1 \leqq i \leqq N) は座標 X_i に位置する.

ビ太郎は,これから JOI 市のすべての観光地を訪ねようとしている.貪欲をスローガンとして生きているビ太郎は,すべての観光地を訪ねるまで以下の行動を繰り返す.

  • 現在のビ太郎の座標を x としたとき,まだ訪ねていない観光地のうち現在のビ太郎からの距離 |x - X_i| を最小とする観光地 i がある場所まで移動し,その観光地を訪ねる.ただし,そのような観光地が複数ある場合は座標が小さいほうを選ぶ.ここで,|t| は t の絶対値を表す.

しかしビ太郎は,長年の経験から,このような方法で移動を繰り返すと予想外に移動距離が長くなってしまうことがあることを知っていた.移動距離はビ太郎がスタートする座標によって変化することがあるので,Q 個の座標 S_1, S_2, \ldots, S_Q について,その座標からビ太郎がスタートした場合の移動距離を調べることにした.

ビ太郎を助けるために,JOI 市の観光地の情報とビ太郎がスタートする座標の候補の情報が与えられたとき,それぞれの候補について,その座標からビ太郎がスタートした場合の移動距離を求めるプログラムを作成せよ.


入力

入力は以下の形式で標準入力から与えられる.

N
X_1 X_2 \cdots X_N
Q
S_1
S_2
\vdots
S_Q

出力

標準出力に Q 行出力せよ.j 行目 (1 \leqq j \leqq Q) には,座標 S_j からビ太郎がスタートした場合,すべての観光地を訪ねるまでにビ太郎が移動する距離を出力せよ.

制約

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq Q \leqq 200\,000.
  • 0 \leqq X_i \leqq 10^9 (1 \leqq i \leqq N).
  • X_i < X_{i+1} (1 \leqq i \leqq N - 1).
  • 0 \leqq S_j \leqq 10^9 (1 \leqq j \leqq Q).
  • 入力される値はすべて整数である.

小課題

  1. (5 点) Q = 1,N \leqq 2\,000.
  2. (10 点) Q = 1.
  3. (30 点) X_{i+1} - X_i \leqq 100 (1 \leqq i \leqq N - 1).
  4. (55 点) 追加の制約はない.

入力例 1

5
0 5 6 7 9
1
7

出力例 1

15

ビ太郎が座標 7 からスタートすると,ビ太郎は以下の手順で観光地を訪ねる.

  1. まだ訪ねていない観光地は観光地 1, 2, 3, 4, 5 であり,ビ太郎からの距離はそれぞれ 7, 2, 1, 0, 2 である.このうちビ太郎からの距離が最小の観光地は観光地 4 であるから,ビ太郎は座標 7 に留まり,観光地 4 を訪ねる.
  2. まだ訪ねていない観光地は観光地 1, 2, 3, 5 であり,ビ太郎からの距離はそれぞれ 7, 2, 1, 2 である.このうちビ太郎からの距離が最小の観光地は観光地 3 であるから,ビ太郎は座標 7 から座標 6 へ移動し,観光地 3 を訪ねる.
  3. まだ訪ねていない観光地は観光地 1, 2, 5 であり,ビ太郎からの距離はそれぞれ 6, 1, 3 である.このうちビ太郎からの距離が最小の観光地は観光地 2 であるから,ビ太郎は座標 6 から座標 5 へ移動し,観光地 2 を訪ねる.
  4. まだ訪ねていない観光地は観光地 1, 5 であり,ビ太郎からの距離はそれぞれ 5, 4 である.このうちビ太郎からの距離が最小の観光地は観光地 5 であるから,ビ太郎は座標 5 から座標 9 へ移動し,観光地 5 を訪ねる.
  5. まだ訪ねていない観光地は観光地 1 である.このうちビ太郎からの距離が最小の観光地は観光地 1 であるから,ビ太郎は座標 9 から座標 0 へ移動し,観光地 1 を訪ねる.

ビ太郎が移動した距離は合計で 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

出力例 2

9
10
11
12
13
14
15
16
17
9

この入力例は小課題 3, 4 の制約を満たす.


Source Name

JOI 2022/2023 春季トレーニング Contest Day4 問題3