Bitaro의 여행

JOI 시에는 실수 수직선으로 볼 수 있을 만큼 아주 긴 도로가 있다. 도로 위의 위치는 실수 좌표로 나타낸다. JOI 시에는 도로를 따라 관광지가 $N$곳 있으며, 좌표가 작은 순서대로 $1$번부터 $N$번까지 번호가 붙어 있다. $i$번 관광지($1 \le i \le N$)의 좌표는 $X_i$이다.

비타로는 JOI 시의 모든 관광지를 방문하려고 한다. 그의 인생 좌우명은 "greedy"여서, 모든 관광지를 방문할 때까지 다음 절차를 반복한다.

• 비타로의 현재 좌표를 $x$라 하자. 아직 방문하지 않은 관광지 중에서 거리 $|x - X_i|$가 최소인 관광지 $i$를 고른다. 비타로는 관광지 $i$로 이동해 방문한다. 최소 거리인 관광지가 여럿이면 좌표가 더 작은 관광지로 이동한다.

여기서 $|t|$는 $t$의 절댓값이다.

비타로는 오랜 경험으로, 이 방식대로 이동하면 총 이동 거리가 예상보다 길어질 수 있다는 것을 알고 있다. 총 이동 거리는 출발 좌표에 따라 달라진다. 그는 출발 좌표 후보 $Q$개 $S_1, S_2, \dots, S_Q$ 각각에서 출발했을 때, 모든 관광지를 방문할 때까지의 총 이동 거리를 알고 싶어 한다.

JOI 시의 정보와 출발 좌표 후보가 주어졌을 때, 각 후보에서 출발한 경우의 총 이동 거리를 계산하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다.

$N$

$X_1$ $X_2$ $\cdots$ $X_N$

$Q$

$S_1$

$S_2$

$\vdots$

$S_Q$

표준 출력에 $Q$줄을 출력한다. $j$번째 줄에는 비타로가 좌표 $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$).
• 주어진 값은 모두 정수이다.