En la ciudad de JOI hay una carretera muy larga, que puede considerarse como la recta real. Cada posición en la carretera se representa mediante una coordenada real. A lo largo de ella hay $N$ lugares turísticos, numerados de $1$ a $N$ en orden creciente de sus coordenadas. La coordenada del lugar turístico $i$ ($1 \le i \le N$) es $X_i$.

Bitaro visitará todos los lugares turísticos de la ciudad de JOI. Como «voraz» es el lema de su vida, repetirá el siguiente procedimiento hasta haberlos visitado todos.

• Sea $x$ la coordenada actual de Bitaro. Entre los lugares turísticos que aún no ha visitado, elige un lugar $i$ cuya distancia $|x-X_i|$ desde su posición actual sea mínima. A continuación, Bitaro se desplaza a la posición del lugar turístico $i$ y lo visita. Si hay varios lugares que cumplen esa condición, se dirige al que tiene la coordenada más pequeña. Aquí, $|t|$ es el valor absoluto de $t$.

Sin embargo, gracias a sus muchos años de experiencia, Bitaro sabe que, si repite este procedimiento, la distancia total recorrida puede ser mayor de lo que esperaba. Como esta distancia varía según la coordenada inicial, quiere conocer la distancia total que recorrerá hasta visitar todos los lugares turísticos si comienza en cada una de las $Q$ coordenadas iniciales candidatas $S_1,S_2,\ldots,S_Q$.

Para ayudar a Bitaro, escribe un programa que, dada la información de la ciudad de JOI y las coordenadas iniciales candidatas, calcule la distancia total recorrida si comienza en cada una de ellas.

Entrada

Lee los siguientes datos de la entrada estándar.

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

Salida

Escribe $Q$ líneas en la salida estándar. La línea $j$ ($1 \le j \le Q$) debe contener la distancia total recorrida si Bitaro comienza en la coordenada $S_j$.

Restricciones

• $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$).
• Todos los valores dados son enteros.

Subtareas

1. (5 puntos) $Q=1$, $N \le 2\,000$.
2. (10 puntos) $Q=1$.
3. (30 puntos) $X_{i+1}-X_i \le 100$ ($1 \le i \le N-1$).
4. (55 puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

5
0 5 6 7 9
1
7

Salida 1

15

Nota

Si Bitaro comienza en la coordenada $7$, visita todos los lugares turísticos de la siguiente manera.

1. Aún no ha visitado los lugares turísticos $1,2,3,4,5$, cuyas distancias desde su posición actual son $7,2,1,0,2$, respectivamente. Como el lugar turístico $4$ es el más cercano, permanece en la coordenada $7$ y visita el lugar turístico $4$.
2. Aún no ha visitado los lugares turísticos $1,2,3,5$, cuyas distancias desde su posición actual son $7,2,1,2$, respectivamente. Como el lugar turístico $3$ es el más cercano, se desplaza de la coordenada $7$ a la coordenada $6$ y visita el lugar turístico $3$.
3. Aún no ha visitado los lugares turísticos $1,2,5$, cuyas distancias desde su posición actual son $6,1,3$, respectivamente. Como el lugar turístico $2$ es el más cercano, se desplaza de la coordenada $6$ a la coordenada $5$ y visita el lugar turístico $2$.
4. Aún no ha visitado los lugares turísticos $1,5$, cuyas distancias desde su posición actual son $5,4$, respectivamente. Como el lugar turístico $5$ es el más cercano, se desplaza de la coordenada $5$ a la coordenada $9$ y visita el lugar turístico $5$.
5. Aún no ha visitado el lugar turístico $1$. Como este es el más cercano, se desplaza de la coordenada $9$ a la coordenada $0$ y visita el lugar turístico $1$.

Como la distancia total recorrida por Bitaro es $15$, imprime $15$.

Este ejemplo cumple las restricciones de todas las subtareas.

Entrada 2

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

Salida 2

9
10
11
12
13
14
15
16
17
9

Nota

Este ejemplo cumple las restricciones de las subtareas $3,4$.