Thành phố JOI có một con đường rất dài, có thể xem như trục số thực. Một vị trí trên đường được biểu diễn bằng một tọa độ thực. Dọc con đường có $N$ điểm tham quan, được đánh số từ $1$ đến $N$ theo thứ tự tọa độ tăng dần. Tọa độ của điểm tham quan thứ $i$ ($1\le i\le N$) là $X_i$.

Bitaro sẽ ghé thăm tất cả các điểm tham quan ở Thành phố JOI. Vì «tham lam» là phương châm sống của mình, cậu sẽ lặp lại quy trình sau cho đến khi ghé thăm hết mọi điểm tham quan.

• Gọi $x$ là tọa độ hiện tại của Bitaro. Trong các điểm tham quan chưa ghé thăm, chọn điểm $i$ có khoảng cách $|x-X_i|$ từ vị trí hiện tại của Bitaro nhỏ nhất. Sau đó, Bitaro di chuyển đến vị trí của điểm tham quan $i$ và ghé thăm nó. Nếu có nhiều điểm như vậy, cậu chọn điểm có tọa độ nhỏ nhất. Ở đây, $|t|$ là giá trị tuyệt đối của $t$.

Tuy nhiên, nhờ nhiều năm kinh nghiệm, Bitaro biết rằng nếu di chuyển bằng cách lặp lại quy trình trên, tổng quãng đường có thể dài hơn dự kiến. Vì tổng quãng đường thay đổi theo tọa độ xuất phát, cậu muốn biết tổng quãng đường cho đến khi ghé thăm hết mọi điểm tham quan nếu xuất phát từ mỗi tọa độ trong $Q$ tọa độ ứng viên $S_1,S_2,\ldots,S_Q$.

Để giúp Bitaro, hãy viết chương trình tính tổng quãng đường nếu cậu xuất phát từ mỗi tọa độ ứng viên, khi được cung cấp thông tin về Thành phố JOI và các tọa độ xuất phát ứng viên.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

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

Dữ liệu ra

In $Q$ dòng ra đầu ra chuẩn. Dòng thứ $j$ ($1\le j\le Q$) chứa tổng quãng đường nếu Bitaro xuất phát từ tọa độ $S_j$.

Giới hạn

• $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$).
• Tất cả các giá trị đã cho đều là số nguyên.

Nhiệm vụ con

1. (5 điểm) $Q=1$, $N\le 2\,000$.
2. (10 điểm) $Q=1$.
3. (30 điểm) $X_{i+1}-X_i\le 100$ ($1\le i\le N-1$).
4. (55 điểm) Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

5
0 5 6 7 9
1
7

Dữ liệu ra 1

15

Ghi chú

Nếu Bitaro xuất phát từ tọa độ $7$, cậu ghé thăm tất cả các điểm tham quan như sau.

1. Cậu chưa ghé thăm các điểm tham quan $1,2,3,4,5$, và khoảng cách từ vị trí hiện tại của Bitaro lần lượt là $7,2,1,0,2$. Vì điểm tham quan $4$ gần Bitaro nhất, cậu ở nguyên tọa độ $7$ và ghé thăm điểm $4$.
2. Cậu chưa ghé thăm các điểm tham quan $1,2,3,5$, và khoảng cách từ vị trí hiện tại của Bitaro lần lượt là $7,2,1,2$. Vì điểm tham quan $3$ gần Bitaro nhất, cậu di chuyển từ tọa độ $7$ đến tọa độ $6$ và ghé thăm điểm $3$.
3. Cậu chưa ghé thăm các điểm tham quan $1,2,5$, và khoảng cách từ vị trí hiện tại của Bitaro lần lượt là $6,1,3$. Vì điểm tham quan $2$ gần Bitaro nhất, cậu di chuyển từ tọa độ $6$ đến tọa độ $5$ và ghé thăm điểm $2$.
4. Cậu chưa ghé thăm các điểm tham quan $1,5$, và khoảng cách từ vị trí hiện tại của Bitaro lần lượt là $5,4$. Vì điểm tham quan $5$ gần Bitaro nhất, cậu di chuyển từ tọa độ $5$ đến tọa độ $9$ và ghé thăm điểm $5$.
5. Cậu chỉ còn điểm tham quan $1$ chưa ghé thăm. Vì điểm tham quan $1$ gần Bitaro nhất, cậu di chuyển từ tọa độ $9$ đến tọa độ $0$ và ghé thăm điểm $1$.

Vì tổng quãng đường của Bitaro là 15, in 15.

Ví dụ đầu vào này thỏa mãn giới hạn của tất cả các nhiệm vụ con.

Dữ liệu vào 2

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

Dữ liệu ra 2

9
10
11
12
13
14
15
16
17
9

Ghi chú

Ví dụ đầu vào này thỏa mãn giới hạn của các nhiệm vụ con 3, 4.