Nella città di JOI c'è una strada molto lunga, che può essere considerata come la retta dei numeri reali. Una posizione sulla strada è rappresentata da una coordinata reale. Nella città di JOI ci sono $N$ luoghi turistici lungo la strada, numerati da $1$ a $N$ in ordine crescente delle coordinate. La coordinata dell'$i$-esimo luogo turistico ($1 \le i \le N$) è $X_i$.

Bitaro visiterà tutti i luoghi turistici nella città di JOI. Poiché “greedy” (avido) è il motto della sua vita, egli ripeterà la seguente procedura finché non avrà visitato tutti i luoghi turistici.

• Sia $x$ la coordinata attuale di Bitaro. Tra i luoghi turistici che non ha ancora visitato, si prenda il luogo turistico $i$ per cui la distanza $|x-X_i|$ dalla posizione attuale di Bitaro assume il valore minimo. Quindi Bitaro si sposta nella posizione del luogo turistico $i$ e lo visita. Se ci sono più luoghi turistici di questo tipo, si sposta nel luogo turistico la cui coordinata è minore rispetto agli altri. Qui, $|t|$ è il valore assoluto di $t$.

Tuttavia, grazie a lunghi anni di esperienza, Bitaro sa che se si muove ripetendo la procedura sopra descritta, la distanza totale percorsa potrebbe essere più lunga di quanto si aspettasse. Poiché la distanza totale percorsa varia a seconda della coordinata di partenza, vuole conoscere la distanza totale percorsa fino a visitare tutti i luoghi turistici se parte da ciascuna delle $Q$ coordinate di partenza candidate $S_1,S_2,\ldots,S_Q$.

Per aiutare Bitaro, scrivi un programma che calcoli la distanza totale percorsa se parte da ciascuna delle coordinate di partenza candidate, date le informazioni sulla città di JOI e le coordinate di partenza candidate.

Input

Leggi i seguenti dati dallo standard input.

N
X_1 X_2 ... X_N
Q
S_1
S_2
...
S_Q

Output

Scrivi $Q$ righe sullo standard output. La $j$-esima riga ($1 \le j \le Q$) di output deve contenere la distanza totale percorsa se Bitaro parte dalla coordinata $S_j$.

Vincoli

• $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$).
• I valori dati sono tutti interi.

Subtask

1. (5 punti) $Q=1$, $N \le 2\,000$.
2. (10 punti) $Q=1$.
3. (30 punti) $X_{i+1}-X_i \le 100$ ($1 \le i \le N-1$).
4. (55 punti) Nessun vincolo aggiuntivo.

Esempi

Input 1

5
0 5 6 7 9
1
7

Output 1

15

Nota

Se Bitaro parte dalla coordinata $7$, visita tutti i luoghi turistici come segue.

1. Non ha ancora visitato i luoghi turistici $1,2,3,4,5$, e le distanze dalla posizione attuale di Bitaro sono rispettivamente $7,2,1,0,2$. Poiché il luogo turistico $4$ è il luogo turistico più vicino a Bitaro, egli rimane alla coordinata $7$ e visita il luogo turistico $4$.
2. Non ha ancora visitato i luoghi turistici $1,2,3,5$, e le distanze dalla posizione attuale di Bitaro sono rispettivamente $7,2,1,2$. Poiché il luogo turistico $3$ è il luogo turistico più vicino a Bitaro, egli si sposta dalla coordinata $7$ alla coordinata $6$ e visita il luogo turistico $3$.
3. Non ha ancora visitato i luoghi turistici $1,2,5$, e le distanze dalla posizione attuale di Bitaro sono rispettivamente $6,1,3$. Poiché il luogo turistico $2$ è il luogo turistico più vicino a Bitaro, egli si sposta dalla coordinata $6$ alla coordinata $5$ e visita il luogo turistico $2$.
4. Non ha ancora visitato i luoghi turistici $1,5$, e le distanze dalla posizione attuale di Bitaro sono rispettivamente $5,4$. Poiché il luogo turistico $5$ è il luogo turistico più vicino a Bitaro, egli si sposta dalla coordinata $5$ alla coordinata $9$ e visita il luogo turistico $5$.
5. Non ha ancora visitato il luogo turistico $1$. Poiché il luogo turistico $1$ è il luogo turistico più vicino a Bitaro, egli si sposta dalla coordinata $9$ alla coordinata $0$ e visita il luogo turistico $1$.

Poiché la distanza totale percorsa da Bitaro è $15$, stampa 15.

Questo input di esempio soddisfa i vincoli di tutti i subtask.

Input 2

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

Output 2

9
10
11
12
13
14
15
16
17
9

Nota

Questo input di esempio soddisfa i vincoli dei Subtask $3,4$.