In der Stadt JOI gibt es eine sehr lange Straße, die als reelle Zahlengerade betrachtet werden kann. Eine Position auf der Straße wird durch eine reelle Koordinate dargestellt. Entlang der Straße gibt es $N$ Sehenswürdigkeiten, die in aufsteigender Reihenfolge ihrer Koordinaten von $1$ bis $N$ nummeriert sind. Die Koordinate der $i$-ten Sehenswürdigkeit ($1 \le i \le N$) ist $X_i$.

Bitaro wird alle Sehenswürdigkeiten in der Stadt JOI besuchen. Da „gierig“ sein Lebensmotto ist, wiederholt er das folgende Verfahren, bis er alle Sehenswürdigkeiten besucht hat.

• Sei $x$ Bitaros aktuelle Koordinate. Unter den Sehenswürdigkeiten, die er noch nicht besucht hat, wählt er eine Sehenswürdigkeit $i$, deren Abstand $|x-X_i|$ von seiner aktuellen Position minimal ist. Dann bewegt sich Bitaro zur Position der Sehenswürdigkeit $i$ und besucht sie. Gibt es mehrere solche Sehenswürdigkeiten, geht er zu derjenigen mit der kleinsten Koordinate. Dabei ist $|t|$ der Absolutbetrag von $t$.

Dank langjähriger Erfahrung weiß Bitaro jedoch, dass seine gesamte zurückgelegte Strecke bei wiederholter Anwendung dieses Verfahrens länger als erwartet sein kann. Da die Gesamtstrecke von der Startkoordinate abhängt, möchte er wissen, welche Strecke er bis zum Besuch aller Sehenswürdigkeiten zurücklegt, wenn er an jeder der $Q$ möglichen Startkoordinaten $S_1,S_2,\ldots,S_Q$ beginnt.

Um Bitaro zu helfen, schreibe ein Programm, das anhand der Informationen über die Stadt JOI und der möglichen Startkoordinaten die Gesamtstrecke für jede mögliche Startkoordinate berechnet.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

$$ \begin{array}{llll} N \\ X_1 & X_2 & \cdots & X_N \\ Q \\ S_1 \\ S_2 \\ \vdots \\ S_Q \end{array} $$

Ausgabe

Gib $Q$ Zeilen auf der Standardausgabe aus. Die $j$-te Zeile ($1 \le j \le Q$) soll die gesamte zurückgelegte Strecke enthalten, wenn Bitaro bei der Koordinate $S_j$ beginnt.

Beschränkungen

• $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$).
• Alle gegebenen Werte sind ganze Zahlen.

Teilaufgaben

1. (5 Punkte) $Q=1$, $N \le 2\,000$.
2. (10 Punkte) $Q=1$.
3. (30 Punkte) $X_{i+1}-X_i \le 100$ ($1 \le i \le N-1$).
4. (55 Punkte) Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

5
0 5 6 7 9
1
7

Ausgabe 1

15

Hinweis

Beginnt Bitaro bei der Koordinate $7$, besucht er alle Sehenswürdigkeiten wie folgt.

1. Er hat die Sehenswürdigkeiten $1,2,3,4,5$ noch nicht besucht, und ihre Abstände von seiner aktuellen Position sind der Reihe nach $7,2,1,0,2$. Da die Sehenswürdigkeit $4$ Bitaro am nächsten liegt, bleibt er bei der Koordinate $7$ und besucht die Sehenswürdigkeit $4$.
2. Er hat die Sehenswürdigkeiten $1,2,3,5$ noch nicht besucht, und ihre Abstände von seiner aktuellen Position sind der Reihe nach $7,2,1,2$. Da die Sehenswürdigkeit $3$ Bitaro am nächsten liegt, bewegt er sich von der Koordinate $7$ zur Koordinate $6$ und besucht die Sehenswürdigkeit $3$.
3. Er hat die Sehenswürdigkeiten $1,2,5$ noch nicht besucht, und ihre Abstände von seiner aktuellen Position sind der Reihe nach $6,1,3$. Da die Sehenswürdigkeit $2$ Bitaro am nächsten liegt, bewegt er sich von der Koordinate $6$ zur Koordinate $5$ und besucht die Sehenswürdigkeit $2$.
4. Er hat die Sehenswürdigkeiten $1,5$ noch nicht besucht, und ihre Abstände von seiner aktuellen Position sind der Reihe nach $5,4$. Da die Sehenswürdigkeit $5$ Bitaro am nächsten liegt, bewegt er sich von der Koordinate $5$ zur Koordinate $9$ und besucht die Sehenswürdigkeit $5$.
5. Er hat die Sehenswürdigkeit $1$ noch nicht besucht. Da die Sehenswürdigkeit $1$ Bitaro am nächsten liegt, bewegt er sich von der Koordinate $9$ zur Koordinate $0$ und besucht die Sehenswürdigkeit $1$.

Da Bitaros Gesamtstrecke $15$ beträgt, gib $15$ aus.

Diese Beispieleingabe erfüllt die Beschränkungen aller Teilaufgaben.

Eingabe 2

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

Ausgabe 2

9
10
11
12
13
14
15
16
17
9

Hinweis

Diese Beispieleingabe erfüllt die Beschränkungen der Teilaufgaben $3,4$.