JOI City 有一條好長嘅路，可以睇成一條實數數線。路上嘅位置用實數座標表示。JOI City 沿住呢條路有 $N$ 個景點，按座標由細到大編號做 $1$ 至 $N$。第 $i$ 個景點（$1\le i\le N$）嘅座標係 $X_i$。

Bitaro 會遊覽 JOI City 所有景點。由於「貪心」係佢嘅人生口號，佢會重複以下步驟，直到遊覽晒所有景點。

• 設 Bitaro 而家嘅座標係 $x$。喺佢仲未遊覽嘅景點當中，揀一個同佢而家位置嘅距離 $|x-X_i|$ 最細嘅景點 $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 嘅限制。