W JOI City znajduje się bardzo długa droga, którą można utożsamić z osią liczb rzeczywistych. Położenie na drodze jest opisane współrzędną będącą liczbą rzeczywistą. Wzdłuż drogi znajduje się $N$ atrakcji turystycznych, ponumerowanych od $1$ do $N$ w kolejności rosnących współrzędnych. Współrzędna $i$-tej atrakcji $(1\le i\le N)$ wynosi $X_i$.

Bitaro zamierza odwiedzić wszystkie atrakcje turystyczne w JOI City. Ponieważ jego życiowym mottem jest „zachłanność”, będzie powtarzał następującą procedurę, dopóki nie odwiedzi wszystkich atrakcji.

• Niech $x$ oznacza aktualną współrzędną Bitaro. Spośród jeszcze nieodwiedzonych atrakcji wybiera on atrakcję $i$, dla której odległość $|x-X_i|$ od jego aktualnego położenia jest najmniejsza. Następnie przemieszcza się do tej atrakcji i ją odwiedza. Jeśli takich atrakcji jest więcej niż jedna, wybiera tę o najmniejszej współrzędnej. Tutaj $|t|$ oznacza wartość bezwzględną $t$.

Jednak dzięki wieloletniemu doświadczeniu Bitaro wie, że poruszając się według powyższej procedury, może pokonać większą łączną odległość, niż oczekiwał. Ponieważ łączna odległość zależy od współrzędnej początkowej, chce poznać odległość, jaką pokona do odwiedzenia wszystkich atrakcji, jeśli rozpocznie z każdej z $Q$ rozważanych współrzędnych początkowych $S_1,S_2,\ldots,S_Q$.

Aby pomóc Bitaro, napisz program, który na podstawie informacji o JOI City i rozważanych współrzędnych początkowych obliczy łączną pokonaną odległość dla każdej z nich.

Wejście

Wczytaj ze standardowego wejścia następujące dane:

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

Wyjście

Wypisz $Q$ wierszy na standardowe wyjście. W $j$-tym wierszu $(1\le j\le Q)$ powinna znaleźć się łączna odległość, jaką pokona Bitaro, jeśli rozpocznie ze współrzędnej $S_j$.

Ograniczenia

• $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)$.
• Wszystkie podane wartości są liczbami całkowitymi.

Podzadania

1. ($5$ punktów) $Q=1$, $N\le 2000$.
2. ($10$ punktów) $Q=1$.
3. ($30$ punktów) $X_{i+1}-X_i\le 100$ $(1\le i\le N-1)$.
4. ($55$ punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

5
0 5 6 7 9
1
7

Wyjście 1

15

Uwagi

Jeśli Bitaro rozpocznie ze współrzędnej $7$, odwiedzi wszystkie atrakcje w następujący sposób.

1. Nie odwiedził jeszcze atrakcji $1,2,3,4,5$, których odległości od jego aktualnego położenia wynoszą odpowiednio $7,2,1,0,2$. Najbliższa jest atrakcja $4$, więc pozostaje przy współrzędnej $7$ i odwiedza atrakcję $4$.
2. Nie odwiedził jeszcze atrakcji $1,2,3,5$, których odległości od jego aktualnego położenia wynoszą odpowiednio $7,2,1,2$. Najbliższa jest atrakcja $3$, więc przemieszcza się ze współrzędnej $7$ do współrzędnej $6$ i odwiedza atrakcję $3$.
3. Nie odwiedził jeszcze atrakcji $1,2,5$, których odległości od jego aktualnego położenia wynoszą odpowiednio $6,1,3$. Najbliższa jest atrakcja $2$, więc przemieszcza się ze współrzędnej $6$ do współrzędnej $5$ i odwiedza atrakcję $2$.
4. Nie odwiedził jeszcze atrakcji $1,5$, których odległości od jego aktualnego położenia wynoszą odpowiednio $5,4$. Najbliższa jest atrakcja $5$, więc przemieszcza się ze współrzędnej $5$ do współrzędnej $9$ i odwiedza atrakcję $5$.
5. Nie odwiedził jeszcze atrakcji $1$. Jest ona najbliższą nieodwiedzoną atrakcją, więc przemieszcza się ze współrzędnej $9$ do współrzędnej $0$ i odwiedza atrakcję $1$.

Łączna odległość pokonana przez Bitaro wynosi $15$, zatem należy wypisać $15$.

Ten przykład spełnia ograniczenia wszystkich podzadań.

Wejście 2

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

Wyjście 2

9
10
11
12
13
14
15
16
17
9

Uwagi

Ten przykład spełnia ograniczenia podzadań $3,4$.