JOI-kaupungissa on hyvin pitkä tie, jota voidaan pitää reaalilukusuorana. Sijaintia tiellä esitetään reaalilukukoordinaatilla. JOI-kaupungissa on tien varrella $N$ nähtävyyttä, jotka on numeroitu $1$:stä $N$:ään koordinaattien mukaisessa nousevassa järjestyksessä. $i$:nnen nähtävyyden ($1 \le i \le N$) koordinaatti on $X_i$.

Bitaro aikoo vierailla kaikissa JOI-kaupungin nähtävyyksissä. Koska ”ahne” (greedy) on hänen elämänsä tunnuslause, hän toistaa seuraavia toimenpiteitä, kunnes hän on vieraillut kaikissa nähtävyyksissä.

• Olkoon $x$ Bitaron nykyinen koordinaatti. Niiden nähtävyyksien joukosta, joissa hän ei ole vielä vieraillut, valitaan nähtävyys $i$, jolle etäisyys $|x-X_i|$ Bitaron nykyisestä sijainnista saa pienimmän arvon. Sitten Bitaro siirtyy nähtävyyden $i$ sijaintiin ja vierailee siellä. Jos tällaisia nähtävyyksiä on enemmän kuin yksi, hän siirtyy siihen nähtävyyteen, jonka koordinaatti on pienempi kuin muiden. Tässä $|t|$ on luvun $t$ itseisarvo.

Pitkän kokemuksensa ansiosta Bitaro kuitenkin tietää, että jos hän liikkuu toistamalla yllä olevia toimenpiteitä, kokonaismatka voi olla pidempi kuin hän odotti. Koska kokonaismatka vaihtelee lähtökoordinaatin mukaan, hän haluaa tietää kokonaismatkan siihen asti, kunnes hän on vieraillut kaikissa nähtävyyksissä, jos hän lähtee liikkeelle kustakin $Q$:sta lähtökoordinaattiehdokkaasta $S_1,S_2,\ldots,S_Q$.

Auttaaksesi Bitaroa kirjoita ohjelma, joka laskee kokonaismatkan, jos hän lähtee liikkeelle kustakin lähtökoordinaattiehdokkaasta, kun annetaan JOI-kaupungin tiedot ja lähtökoordinaattiehdokkaat.

Syöte

Lue seuraavat tiedot vakiosyötteestä (standard input).

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

Tuloste

Kirjoita $Q$ riviä vakiotulosteeseen (standard output). Tulosteen $j$:nnen rivin ($1 \le j \le Q$) tulee sisältää kokonaismatka, jos Bitaro lähtee liikkeelle koordinaatista $S_j$.

Rajoitukset

• $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$).
• Kaikki annetut arvot ovat kokonaislukuja.

Osatehtävät

1. (5 pistettä) $Q=1$, $N \le 2\,000$.
2. (10 pistettä) $Q=1$.
3. (30 pistettä) $X_{i+1}-X_i \le 100$ ($1 \le i \le N-1$).
4. (55 pistettä) Ei lisärajoituksia.

Esimerkit

Syöte 1

5
0 5 6 7 9
1
7

Tuloste 1

15

Huomautus

Jos Bitaro lähtee liikkeelle koordinaatista $7$, hän vierailee kaikissa nähtävyyksissä seuraavasti.

1. Hän ei ole vielä vieraillut nähtävyyksissä $1,2,3,4,5$, ja etäisyydet Bitaron nykyisestä sijainnista ovat vastaavasti $7,2,1,0,2$. Koska nähtävyys $4$ on Bitaroa lähinnä oleva nähtävyys, hän pysyy koordinaatissa $7$ ja vierailee nähtävyydessä $4$.
2. Hän ei ole vielä vieraillut nähtävyyksissä $1,2,3,5$, ja etäisyydet Bitaron nykyisestä sijainnista ovat vastaavasti $7,2,1,2$. Koska nähtävyys $3$ on Bitaroa lähinnä oleva nähtävyys, hän siirtyy koordinaatista $7$ koordinaattiin $6$ ja vierailee nähtävyydessä $3$.
3. Hän ei ole vielä vieraillut nähtävyyksissä $1,2,5$, ja etäisyydet Bitaron nykyisestä sijainnista ovat vastaavasti $6,1,3$. Koska nähtävyys $2$ on Bitaroa lähinnä oleva nähtävyys, hän siirtyy koordinaatista $6$ koordinaattiin $5$ ja vierailee nähtävyydessä $2$.
4. Hän ei ole vielä vieraillut nähtävyyksissä $1,5$, ja etäisyydet Bitaron nykyisestä sijainnista ovat vastaavasti $5,4$. Koska nähtävyys $5$ on Bitaroa lähinnä oleva nähtävyys, hän siirtyy koordinaatista $5$ koordinaattiin $9$ ja vierailee nähtävyydessä $5$.
5. Hän ei ole vielä vieraillut nähtävyydessä $1$. Koska nähtävyys $1$ on Bitaroa lähinnä oleva nähtävyys, hän siirtyy koordinaatista $9$ koordinaattiin $0$ ja vierailee nähtävyydessä $1$.

Koska Bitaron kokonaismatka on $15$, tulosta 15.

Tämä esimerkkisyöte täyttää kaikkien osatehtävien rajoitukset.

Syöte 2

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

Tuloste 2

9
10
11
12
13
14
15
16
17
9

Huomautus

Tämä esimerkkisyöte täyttää osatehtävien $3,4$ rajoitukset.