Det er en veldig lang vei i JOI-byen, som kan betraktes som den reelle tallinjen. En posisjon på veien representeres av en reell koordinat. I JOI-byen er det $N$ severdigheter langs veien, nummerert fra $1$ til $N$ i stigende rekkefølge etter koordinatene. Koordinaten til den $i$-te severdigheten ($1 \le i \le N$) er $X_i$.

Bitaro skal besøke alle severdighetene i JOI-byen. Siden «grådig» (greedy) er hans livsmotto, vil han gjenta følgende prosedyrer til han har besøkt alle severdighetene.

• La $x$ være Bitaros nåværende koordinat. Blant severdighetene han ennå ikke har besøkt, velg severdigheten $i$ der avstanden $|x-X_i|$ fra Bitaros nåværende posisjon antar en minimumsverdi. Deretter flytter Bitaro seg til posisjonen til severdigheten $i$, og besøker den. Hvis det er mer enn én slik severdighet, flytter han seg til severdigheten hvis koordinat er mindre enn de andres. Her er $|t|$ absoluttverdien av $t$.

Takket være mange års erfaring vet Bitaro imidlertid at hvis han flytter seg ved å gjenta prosedyrene ovenfor, kan den totale reisedistansen bli lengre enn han forventet. Siden den totale reisedistansen varierer avhengig av startkoordinaten, ønsker han å vite den totale reisedistansen til han har besøkt alle severdighetene hvis han starter fra hver av de $Q$ kandidatene til startkoordinater $S_1,S_2,\ldots,S_Q$.

For å hjelpe Bitaro, skriv et program som beregner den totale reisedistansen hvis han starter fra hver av kandidatene til startkoordinater, gitt informasjon om JOI-byen og kandidater til startkoordinater.

Inndata

Les følgende data fra standard inndata (standard input).

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

Utdata

Skriv $Q$ linjer til standard utdata (standard output). Den $j$-te linjen ($1 \le j \le Q$) av utdata skal inneholde den totale reisedistansen hvis Bitaro starter fra koordinaten $S_j$.

Begrensninger

• $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 oppgitte verdier er heltall.

Deloppgaver

1. (5 poeng) $Q=1$, $N \le 2\,000$.
2. (10 poeng) $Q=1$.
3. (30 poeng) $X_{i+1}-X_i \le 100$ ($1 \le i \le N-1$).
4. (55 poeng) Ingen ytterligere begrensninger.

Eksempler

Inndata 1

5
0 5 6 7 9
1
7

Utdata 1

15

Forklaring

Hvis Bitaro starter fra koordinaten $7$, besøker han alle severdighetene som følger.

1. Han har ennå ikke besøkt severdighetene $1,2,3,4,5$, og avstandene fra Bitaros nåværende posisjon er henholdsvis $7,2,1,0,2$. Siden severdigheten $4$ er den nærmeste severdigheten fra Bitaro, blir han værende på koordinaten $7$ og besøker severdigheten $4$.
2. Han har ennå ikke besøkt severdighetene $1,2,3,5$, og avstandene fra Bitaros nåværende posisjon er henholdsvis $7,2,1,2$. Siden severdigheten $3$ er den nærmeste severdigheten fra Bitaro, flytter han seg fra koordinaten $7$ til koordinaten $6$ og besøker severdigheten $3$.
3. Han har ennå ikke besøkt severdighetene $1,2,5$, og avstandene fra Bitaros nåværende posisjon er henholdsvis $6,1,3$. Siden severdigheten $2$ er den nærmeste severdigheten fra Bitaro, flytter han seg fra koordinaten $6$ til koordinaten $5$ og besøker severdigheten $2$.
4. Han har ennå ikke besøkt severdighetene $1,5$, og avstandene fra Bitaros nåværende posisjon er henholdsvis $5,4$. Siden severdigheten $5$ er den nærmeste severdigheten fra Bitaro, flytter han seg fra koordinaten $5$ til koordinaten $9$ og besøker severdigheten $5$.
5. Han har ennå ikke besøkt severdigheten $1$. Siden severdigheten $1$ er den nærmeste severdigheten fra Bitaro, flytter han seg fra koordinaten $9$ til koordinaten $0$ og besøker severdigheten $1$.

Siden Bitaros totale reisedistanse er $15$, skriv ut 15.

Disse eksempeldataene tilfredsstiller begrensningene i alle deloppgavene.

Inndata 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

Forklaring

Disse eksempeldataene tilfredsstiller begrensningene i deloppgavene $3,4$.