I JOI-staden finns det en mycket lång väg, som kan betraktas som den reella tallinjen. En position på vägen representeras av en reell koordinat. I JOI-staden finns det $N$ sevärdheter längs vägen, numrerade från $1$ till $N$ i stigande ordning efter koordinaterna. Koordinaten för den $i$:te sevärdheten ($1 \le i \le N$) är $X_i$.

Bitaro ska besöka alla sevärdheterna i JOI-staden. Eftersom ”girig” (greedy) är hans livsmotto kommer han att upprepa följande procedur tills han har besökt alla sevärdheterna.

• Låt $x$ vara Bitaros nuvarande koordinat. Bland de sevärdheter han ännu inte har besökt, välj den sevärdhet $i$ där avståndet $|x-X_i|$ från Bitaros nuvarande position antar sitt minsta värde. Därefter förflyttar sig Bitaro till sevärdheten $i$:s position och besöker den. Om det finns mer än en sådan sevärdhet förflyttar han sig till den sevärdhet vars koordinat är mindre än de andras. Här är $|t|$ absolutbeloppet av $t$.

Tack vare många års erfarenhet vet Bitaro dock att om han förflyttar sig genom att upprepa ovanstående procedur kan den totala ressträckan bli längre än han förväntat sig. Eftersom den totala ressträckan varierar beroende på startkoordinaten vill han veta den totala ressträckan tills han har besökt alla sevärdheterna om han startar från var och en av de $Q$ kandidaterna till startkoordinater $S_1,S_2,\ldots,S_Q$.

För att hjälpa Bitaro, skriv ett program som beräknar den totala ressträckan om han startar från var och en av kandidaterna till startkoordinater, givet information om JOI-staden och kandidaterna till startkoordinater.

Indata

Läs följande data från standard inmatning (standard input).

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

Utdata

Skriv $Q$ rader till standard utmatning (standard output). Den $j$:te raden ($1 \le j \le Q$) av utdata ska innehålla den totala ressträckan om Bitaro startar från koordinaten $S_j$.

Begränsningar

• $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$).
• Alla givna värden är heltal.

Deluppgifter

1. (5 poäng) $Q=1$, $N \le 2\,000$.
2. (10 poäng) $Q=1$.
3. (30 poäng) $X_{i+1}-X_i \le 100$ ($1 \le i \le N-1$).
4. (55 poäng) Inga ytterligare begränsningar.

Exempel

Indata 1

5
0 5 6 7 9
1
7

Utdata 1

15

Förklaring

Om Bitaro startar från koordinaten $7$ besöker han alla sevärdheterna på följande sätt.

1. Han har ännu inte besökt sevärdheterna $1,2,3,4,5$, och avstånden från Bitaros nuvarande position är $7,2,1,0,2$ i nämnd ordning. Eftersom sevärdheten $4$ är den närmaste sevärdheten från Bitaro stannar han på koordinaten $7$ och besöker sevärdheten $4$.
2. Han har ännu inte besökt sevärdheterna $1,2,3,5$, och avstånden från Bitaros nuvarande position är $7,2,1,2$ i nämnd ordning. Eftersom sevärdheten $3$ är den närmaste sevärdheten från Bitaro förflyttar han sig från koordinaten $7$ till koordinaten $6$ och besöker sevärdheten $3$.
3. Han har ännu inte besökt sevärdheterna $1,2,5$, och avstånden från Bitaros nuvarande position är $6,1,3$ i nämnd ordning. Eftersom sevärdheten $2$ är den närmaste sevärdheten från Bitaro förflyttar han sig från koordinaten $6$ till koordinaten $5$ och besöker sevärdheten $2$.
4. Han har ännu inte besökt sevärdheterna $1,5$, och avstånden från Bitaros nuvarande position är $5,4$ i nämnd ordning. Eftersom sevärdheten $5$ är den närmaste sevärdheten från Bitaro förflyttar han sig från koordinaten $5$ till koordinaten $9$ och besöker sevärdheten $5$.
5. Han har ännu inte besökt sevärdheten $1$. Eftersom sevärdheten $1$ är den närmaste sevärdheten från Bitaro förflyttar han sig från koordinaten $9$ till koordinaten $0$ och besöker sevärdheten $1$.

Eftersom Bitaros totala ressträcka är $15$, skriv ut 15.

Dessa exempelindata uppfyller begränsningarna för alla deluppgifter.

Indata 2

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

Utdata 2

9
10
11
12
13
14
15
16
17
9

Förklaring

Dessa exempelindata uppfyller begränsningarna för deluppgifterna $3,4$.