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

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

• Пусть текущая координата Bitaro равна $x$. Среди ещё не посещённых достопримечательностей он выбирает достопримечательность $i$, для которой расстояние $|x-X_i|$ от его текущего положения минимально. Затем Bitaro перемещается к достопримечательности $i$ и посещает её. Если таких достопримечательностей несколько, он выбирает ту, координата которой наименьшая. Здесь $|t|$ — абсолютная величина $t$.

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

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

Входные данные

Считайте следующие данные из стандартного ввода.

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

Выходные данные

Выведите $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 2\,000$.
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$ находится ближе всего к Bitaro, он остаётся на координате $7$ и посещает достопримечательность $4$.
2. Он ещё не посетил достопримечательности $1,2,3,5$, расстояния от текущего положения Bitaro до которых равны соответственно $7,2,1,2$. Поскольку достопримечательность $3$ находится ближе всего к Bitaro, он перемещается с координаты $7$ на координату $6$ и посещает достопримечательность $3$.
3. Он ещё не посетил достопримечательности $1,2,5$, расстояния от текущего положения Bitaro до которых равны соответственно $6,1,3$. Поскольку достопримечательность $2$ находится ближе всего к Bitaro, он перемещается с координаты $6$ на координату $5$ и посещает достопримечательность $2$.
4. Он ещё не посетил достопримечательности $1,5$, расстояния от текущего положения Bitaro до которых равны соответственно $5,4$. Поскольку достопримечательность $5$ находится ближе всего к Bitaro, он перемещается с координаты $5$ на координату $9$ и посещает достопримечательность $5$.
5. Он ещё не посетил достопримечательность $1$. Поскольку достопримечательность $1$ находится ближе всего к Bitaro, он перемещается с координаты $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.