2023-sp_Bitaro’s_travel — JOI JOI_spring
Task type: batch | Time limit: 2 s | Memory limit: 1024 MB | Difficulty: 18
Algorithms: optimization, data structures, greedy, simulation

# Bitaro's Travel

![](_page_0_Picture_0.jpeg)

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)  
Spring Training/Qualifying Trial  
March 18–22, 2023 (Komaba, Tokyo)  
Contest 4 - 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<sub>i</sub>*.

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<sub>i</sub>*| 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*<sub>1</sub>, *S*<sub>2</sub>, . . . , *S<sub>Q</sub>*.

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
X1 X2 · · · XN
Q
S1
S2
.
.
.
SQ
```

## Output

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<sub>j</sub>*.

## Constraints

*   1 ≤ *N* ≤ 200 000.
*   1 ≤ *Q* ≤ 200 000.
*   0 ≤ *X<sub>i</sub>* ≤ 10<sup>9</sup> (1 ≤ *i* ≤ *N*).
*   *X<sub>i</sub>* < *X<sub>i+1</sub>* (1 ≤ *i* ≤ *N* − 1).
*   0 ≤ *S<sub>j</sub>* ≤ 10<sup>9</sup> (1 ≤ *j* ≤ *Q*).
*   Given values are all integers.

## Subtasks

1.  (5 points) *Q* = 1, *N* ≤ 2 000.
2.  (10 points) *Q* = 1.
3.  (30 points) *X<sub>i+1</sub>* − *X<sub>i</sub>* ≤ 100 (1 ≤ *i* ≤ *N* − 1).
4.  (55 points) No additional constraints.

## Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :-------------- |
| 5              | 15              |
| 0 5 6 7 9      |                 |
| 1              |                 |
| 7              |                 |

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.

| Sample Input 2       | Sample Output 2 |
| :------------------- | :-------------- |
| 10                   | 9               |
| 1 2 3 4 5 6 7 8 9 10 |                 |
| 10                   | 10              |
| 1                    | 11              |
| 2                    | 12              |
| 3                    | 13              |
| 4                    | 14              |
| 5                    | 15              |
| 6                    | 16              |
| 7                    | 17              |
| 8                    | 9               |
| 9                    |                 |
| 10                   |                 |

This sample input satisfies the constraints of all the subtasks.

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

Starter code: