У JOI City є дуже довга дорога, яку можна вважати числовою прямою дійсних чисел. Положення на дорозі задається дійсною координатою. Уздовж дороги є $N$ туристичних пам'яток, пронумерованих від $1$ до $N$ у порядку зростання координат. Координата $i$-ї пам'ятки $(1\le i\le N)$ дорівнює $X_i$.

Bitaro збирається відвідати всі туристичні пам'ятки JOI City. Оскільки його життєве гасло — «жадібність», він повторюватиме таку процедуру, доки не відвідає всі пам'ятки.

• Нехай $x$ — поточна координата Bitaro. Серед ще не відвіданих пам'яток він вибирає пам'ятку $i$, для якої відстань $|x-X_i|$ від його поточного положення є найменшою. Потім Bitaro переміщується до цієї пам'ятки та відвідує її. Якщо таких пам'яток декілька, він вибирає ту, координата якої найменша. Тут $|t|$ означає абсолютну величину $t$.

Проте завдяки багаторічному досвіду Bitaro знає, що за такого пересування загальна пройдена відстань може виявитися більшою, ніж він очікує. Оскільки загальна відстань залежить від початкової координати, він хоче знати відстань, яку пройде до відвідання всіх пам'яток, якщо почне з кожної з $Q$ можливих початкових координат $S_1,S_2,\ldots,S_Q$.

Щоб допомогти Bitaro, напишіть програму, яка за інформацією про JOI City та можливі початкові координати обчислює загальну пройдену відстань для кожної з них.

Вхідні дані

Прочитайте зі стандартного вводу такі дані:

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

Вихідні дані

Виведіть $Q$ рядків у стандартний вивід. $j$-й рядок $(1\le j\le Q)$ має містити загальну пройдену відстань, якщо Bitaro починає з координати $S_j$.

Обмеження

• $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)$.
• Усі задані значення — цілі числа.

Підзадачі

1. ($5$ балів) $Q=1$, $N\le 2000$.
2. ($10$ балів) $Q=1$.
3. ($30$ балів) $X_{i+1}-X_i\le 100$ $(1\le i\le N-1)$.
4. ($55$ балів) Без додаткових обмежень.

Приклади

Вхідні дані 1

5
0 5 6 7 9
1
7

Вихідні дані 1

15

Примітка

Якщо Bitaro почне з координати $7$, він відвідає всі пам'ятки так.

1. Ще не відвідано пам'ятки $1,2,3,4,5$, відстані до яких від поточного положення Bitaro дорівнюють відповідно $7,2,1,0,2$. Найближчою є пам'ятка $4$, тому він залишається в координаті $7$ та відвідує пам'ятку $4$.
2. Ще не відвідано пам'ятки $1,2,3,5$, відстані до яких від поточного положення Bitaro дорівнюють відповідно $7,2,1,2$. Найближчою є пам'ятка $3$, тому він переміщується з координати $7$ до координати $6$ та відвідує пам'ятку $3$.
3. Ще не відвідано пам'ятки $1,2,5$, відстані до яких від поточного положення Bitaro дорівнюють відповідно $6,1,3$. Найближчою є пам'ятка $2$, тому він переміщується з координати $6$ до координати $5$ та відвідує пам'ятку $2$.
4. Ще не відвідано пам'ятки $1,5$, відстані до яких від поточного положення Bitaro дорівнюють відповідно $5,4$. Найближчою є пам'ятка $5$, тому він переміщується з координати $5$ до координати $9$ та відвідує пам'ятку $5$.
5. Ще не відвідано лише пам'ятку $1$. Вона є найближчою не відвіданою пам'яткою, тому він переміщується з координати $9$ до координати $0$ та відвідує пам'ятку $1$.

Оскільки загальна пройдена Bitaro відстань дорівнює $15$, слід вивести $15$.

Цей приклад задовольняє обмеження всіх підзадач.

Вхідні дані 2

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

Вихідні дані 2

9
10
11
12
13
14
15
16
17
9

Примітка

Цей приклад задовольняє обмеження підзадач $3,4$.