Há uma estrada muito longa na cidade de JOI, que pode ser considerada a reta real. Uma posição na estrada é representada por uma coordenada real. Há $N$ pontos turísticos ao longo da estrada, numerados de $1$ a $N$ em ordem crescente de coordenada. A coordenada do $i$-ésimo ponto turístico ($1 \le i \le N$) é $X_i$.

Bitaro visitará todos os pontos turísticos da cidade de JOI. Como “guloso” é o lema de sua vida, ele repetirá o procedimento a seguir até visitar todos eles.

• Seja $x$ a coordenada atual de Bitaro. Entre os pontos turísticos que ainda não visitou, ele escolhe o ponto $i$ cuja distância $|x-X_i|$ até sua posição atual é mínima. Então, vai até a posição do ponto turístico $i$ e o visita. Se houver mais de um ponto nessas condições, escolhe aquele com a menor coordenada. Aqui, $|t|$ é o valor absoluto de $t$.

No entanto, graças a muitos anos de experiência, Bitaro sabe que, repetindo esse procedimento, a distância total percorrida pode ser maior do que esperava. Como a distância total depende da coordenada inicial, ele quer saber a distância total que percorrerá até visitar todos os pontos turísticos se começar de cada uma das $Q$ coordenadas iniciais candidatas $S_1,S_2,\ldots,S_Q$.

Para ajudar Bitaro, escreva um programa que calcule a distância total percorrida para cada coordenada inicial candidata, dadas as informações sobre a cidade de JOI e as coordenadas iniciais candidatas.

Entrada

Leia os seguintes dados da entrada padrão.

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

Saída

Escreva $Q$ linhas na saída padrão. A $j$-ésima linha ($1 \le j \le Q$) deve conter a distância total percorrida se Bitaro começar na coordenada $S_j$.

Restrições

• $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 os valores fornecidos são inteiros.

Subtarefas

1. (5 pontos) $Q=1$, $N \le 2\,000$.
2. (10 pontos) $Q=1$.
3. (30 pontos) $X_{i+1}-X_i \le 100$ ($1 \le i \le N-1$).
4. (55 pontos) Sem restrições adicionais.

Exemplos

Entrada 1

5
0 5 6 7 9
1
7

Saída 1

15

Explicação

Se Bitaro começar na coordenada 7, visitará todos os pontos turísticos da seguinte maneira.

1. Ele ainda não visitou os pontos turísticos 1, 2, 3, 4, 5, cujas distâncias até sua posição atual são, respectivamente, 7, 2, 1, 0, 2. Como o ponto 4 é o mais próximo, ele permanece na coordenada 7 e visita o ponto 4.
2. Ele ainda não visitou os pontos turísticos 1, 2, 3, 5, cujas distâncias até sua posição atual são, respectivamente, 7, 2, 1, 2. Como o ponto 3 é o mais próximo, ele vai da coordenada 7 à coordenada 6 e visita o ponto 3.
3. Ele ainda não visitou os pontos turísticos 1, 2, 5, cujas distâncias até sua posição atual são, respectivamente, 6, 1, 3. Como o ponto 2 é o mais próximo, ele vai da coordenada 6 à coordenada 5 e visita o ponto 2.
4. Ele ainda não visitou os pontos turísticos 1, 5, cujas distâncias até sua posição atual são, respectivamente, 5, 4. Como o ponto 5 é o mais próximo, ele vai da coordenada 5 à coordenada 9 e visita o ponto 5.
5. Ele ainda não visitou o ponto turístico 1. Como esse é o ponto mais próximo, ele vai da coordenada 9 à coordenada 0 e visita o ponto 1.

Como a distância total percorrida por Bitaro é 15, escreva 15.

Esta entrada de exemplo satisfaz as restrições de todas as subtarefas.

Entrada 2

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

Saída 2

9
10
11
12
13
14
15
16
17
9

Explicação

Esta entrada de exemplo satisfaz as restrições das subtarefas 3 e 4.