Dans la ville de JOI, une très longue route peut être considérée comme la droite des nombres réels. Une position sur cette route est représentée par une coordonnée réelle. Il y a $N$ sites touristiques le long de la route, numérotés de $1$ à $N$ par ordre croissant de leurs coordonnées. La coordonnée du $i$-ème site ($1\le i\le N$) est $X_i$.

Bitaro va visiter tous les sites touristiques de la ville de JOI. Comme « glouton » est sa devise dans la vie, il répétera la procédure suivante jusqu'à les avoir tous visités.

• Soit $x$ la coordonnée actuelle de Bitaro. Parmi les sites qu'il n'a pas encore visités, il choisit le site $i$ dont la distance $|x-X_i|$ à sa position actuelle est minimale. Bitaro se déplace alors à la position du site $i$ et le visite. Si plusieurs sites conviennent, il se rend à celui dont la coordonnée est la plus petite. Ici, $|t|$ désigne la valeur absolue de $t$.

Cependant, grâce à ses longues années d'expérience, Bitaro sait qu'en répétant cette procédure, la distance totale parcourue peut être plus longue que prévu. Comme cette distance dépend de la coordonnée de départ, il veut connaître la distance totale jusqu'à avoir visité tous les sites pour chacun des $Q$ départs possibles $S_1,S_2,\ldots,S_Q$.

Pour aider Bitaro, écrivez un programme qui, à partir des informations sur la ville de JOI et des coordonnées de départ possibles, calcule la distance totale parcourue pour chacune d'elles.

Entrée

Lisez les données suivantes sur l'entrée standard.

$$ \begin{array}{l} N\\ X_1\ X_2\ \cdots\ X_N\\ Q\\ S_1\\ S_2\\ \vdots\\ S_Q \end{array} $$

Sortie

Écrivez $Q$ lignes sur la sortie standard. La $j$-ème ligne ($1\le j\le Q$) doit contenir la distance totale parcourue si Bitaro part de la coordonnée $S_j$.

Contraintes

• $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$).
• Toutes les valeurs fournies sont des entiers.

Sous-tâches

1. (5 points) $Q=1$, $N\le 2\,000$.
2. (10 points) $Q=1$.
3. (30 points) $X_{i+1}-X_i\le 100$ ($1\le i\le N-1$).
4. (55 points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

5
0 5 6 7 9
1
7

Sortie 1

15

Remarque

Si Bitaro part de la coordonnée $7$, il visite tous les sites comme suit.

1. Il n'a pas encore visité les sites $1,2,3,4,5$, dont les distances à sa position actuelle sont respectivement $7,2,1,0,2$. Comme le site $4$ est le plus proche, il reste à la coordonnée $7$ et visite le site $4$.
2. Il n'a pas encore visité les sites $1,2,3,5$, dont les distances à sa position actuelle sont respectivement $7,2,1,2$. Comme le site $3$ est le plus proche, il se déplace de la coordonnée $7$ à la coordonnée $6$ et visite le site $3$.
3. Il n'a pas encore visité les sites $1,2,5$, dont les distances à sa position actuelle sont respectivement $6,1,3$. Comme le site $2$ est le plus proche, il se déplace de la coordonnée $6$ à la coordonnée $5$ et visite le site $2$.
4. Il n'a pas encore visité les sites $1,5$, dont les distances à sa position actuelle sont respectivement $5,4$. Comme le site $5$ est le plus proche, il se déplace de la coordonnée $5$ à la coordonnée $9$ et visite le site $5$.
5. Il n'a pas encore visité le site $1$. Comme ce site est le plus proche, il se déplace de la coordonnée $9$ à la coordonnée $0$ et visite le site $1$.

Comme la distance totale parcourue par Bitaro est $15$, écrivez $15$.

Cet exemple satisfait les contraintes de toutes les sous-tâches.

Entrée 2

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

Sortie 2

9
10
11
12
13
14
15
16
17
9

Remarque

Cet exemple satisfait les contraintes des sous-tâches $3,4$.