Það er mjög langur vegur í JOI-borg, sem líta má á sem rauntalnalínuna. Staðsetning á veginum er táknuð með rauntöluhnitum. Í JOI-borg eru $N$ ferðamannastaðir meðfram veginum, númeraðir frá $1$ til $N$ í hækkandi röð eftir hnitunum. Hnit $i$-ta ferðamannastaðarins ($1 \le i \le N$) er $X_i$.

Bitaro ætlar að heimsækja alla ferðamannastaðina í JOI-borg. Þar sem „gráðugur“ (greedy) er kjörorð lífs hans mun hann endurtaka eftirfarandi skref þar til hann hefur heimsótt alla ferðamannastaðina.

• Látum $x$ vera núverandi hnit Bitaros. Meðal þeirra ferðamannastaða sem hann hefur enn ekki heimsótt skal taka ferðamannastaðinn $i$ þar sem fjarlægðin $|x-X_i|$ frá núverandi staðsetningu Bitaros tekur lágmarksgildi. Síðan færir Bitaro sig á staðsetningu ferðamannastaðarins $i$ og heimsækir hann. Ef það eru fleiri en einn slíkur ferðamannastaður færir hann sig á þann ferðamannastað sem hefur lægra hnit en hinir. Hér er $|t|$ tölugildi (algildi) $t$.

Hins vegar, þökk sé margra ára reynslu, veit Bitaro að ef hann ferðast með því að endurtaka ofangreind skref getur heildarferðavegalengdin orðið lengri en hann bjóst við. Þar sem heildarferðavegalengdin er breytileg eftir upphafshnitinu vill hann vita heildarferðavegalengdina þar til hann hefur heimsótt alla ferðamannastaðina ef hann byrjar á hverju hinna $Q$ mögulegu upphafshnita $S_1,S_2,\ldots,S_Q$.

Til að hjálpa Bitaro, skrifið forrit sem reiknar heildarferðavegalengdina ef hann byrjar á hverju hinna mögulegu upphafshnita, gefnum upplýsingum um JOI-borg og möguleg upphafshnit.

Inntak

Lesið eftirfarandi gögn úr staðalinntaki (standard input).

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

Úttak

Skrifið $Q$ línur í staðalúttak (standard output). $j$-ta línan ($1 \le j \le Q$) í úttakinu á að innihalda heildarferðavegalengdina ef Bitaro byrjar á hnitinu $S_j$.

Skorður

• $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$).
• Öll gefin gildi eru heiltölur.

Undirverkefni

1. (5 stig) $Q=1$, $N \le 2\,000$.
2. (10 stig) $Q=1$.
3. (30 stig) $X_{i+1}-X_i \le 100$ ($1 \le i \le N-1$).
4. (55 stig) Engar viðbótarskorður.

Dæmi

Inntak 1

5
0 5 6 7 9
1
7

Úttak 1

15

Skýring

Ef Bitaro byrjar á hnitinu $7$ heimsækir hann alla ferðamannastaðina á eftirfarandi hátt.

1. Hann hefur enn ekki heimsótt ferðamannastaðina $1,2,3,4,5$, og fjarlægðirnar frá núverandi staðsetningu Bitaros eru $7,2,1,0,2$, í þessari röð. Þar sem ferðamannastaðurinn $4$ er sá ferðamannastaður sem er næstur Bitaro, verður hann kyrr á hnitinu $7$ og heimsækir ferðamannastaðinn $4$.
2. Hann hefur enn ekki heimsótt ferðamannastaðina $1,2,3,5$, og fjarlægðirnar frá núverandi staðsetningu Bitaros eru $7,2,1,2$, í þessari röð. Þar sem ferðamannastaðurinn $3$ er sá ferðamannastaður sem er næstur Bitaro, færir hann sig frá hnitinu $7$ á hnitið $6$ og heimsækir ferðamannastaðinn $3$.
3. Hann hefur enn ekki heimsótt ferðamannastaðina $1,2,5$, og fjarlægðirnar frá núverandi staðsetningu Bitaros eru $6,1,3$, í þessari röð. Þar sem ferðamannastaðurinn $2$ er sá ferðamannastaður sem er næstur Bitaro, færir hann sig frá hnitinu $6$ á hnitið $5$ og heimsækir ferðamannastaðinn $2$.
4. Hann hefur enn ekki heimsótt ferðamannastaðina $1,5$, og fjarlægðirnar frá núverandi staðsetningu Bitaros eru $5,4$, í þessari röð. Þar sem ferðamannastaðurinn $5$ er sá ferðamannastaður sem er næstur Bitaro, færir hann sig frá hnitinu $5$ á hnitið $9$ og heimsækir ferðamannastaðinn $5$.
5. Hann hefur enn ekki heimsótt ferðamannastaðinn $1$. Þar sem ferðamannastaðurinn $1$ er sá ferðamannastaður sem er næstur Bitaro, færir hann sig frá hnitinu $9$ á hnitið $0$ og heimsækir ferðamannastaðinn $1$.

Þar sem heildarferðavegalengd Bitaros er $15$, skrifið út 15.

Þetta sýnidæmi uppfyllir skorður allra undirverkefnanna.

Inntak 2

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

Úttak 2

9
10
11
12
13
14
15
16
17
9

Skýring

Þetta sýnidæmi uppfyllir skorður undirverkefna $3,4$.