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,\ldots,S_Q$ 각각에서 출발했을 때 모든 관광지를 방문할 때까지의 총 이동 거리를 알고 싶어 합니다.

비타로를 돕기 위해, JOI 시의 정보와 출발 좌표 후보들이 주어질 때 각 출발 좌표 후보에서 출발했을 경우의 총 이동 거리를 계산하는 프로그램을 작성하십시오.

입력

표준 입력으로부터 다음 데이터를 읽으십시오.

N
X_1 X_2 ... X_N
Q
S_1
S_2
...
S_Q

출력

표준 출력에 $Q$개의 줄을 출력하십시오. 출력의 $j$번째 줄 ($1 \le j \le Q$)에는 비타로가 좌표 $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

설명

비타로가 좌표 $7$에서 출발하면 다음과 같이 모든 관광지를 방문합니다.

1. 아직 방문하지 않은 관광지는 $1,2,3,4,5$이며, 비타로의 현재 위치로부터의 거리는 각각 $7,2,1,0,2$입니다. 관광지 $4$가 비타로에게서 가장 가까운 관광지이므로, 비타로는 좌표 $7$에 머무르며 관광지 $4$를 방문합니다.
2. 아직 방문하지 않은 관광지는 $1,2,3,5$이며, 비타로의 현재 위치로부터의 거리는 각각 $7,2,1,2$입니다. 관광지 $3$이 비타로에게서 가장 가까운 관광지이므로, 비타로는 좌표 $7$에서 좌표 $6$으로 이동하여 관광지 $3$을 방문합니다.
3. 아직 방문하지 않은 관광지는 $1,2,5$이며, 비타로의 현재 위치로부터의 거리는 각각 $6,1,3$입니다. 관광지 $2$가 비타로에게서 가장 가까운 관광지이므로, 비타로는 좌표 $6$에서 좌표 $5$로 이동하여 관광지 $2$를 방문합니다.
4. 아직 방문하지 않은 관광지는 $1,5$이며, 비타로의 현재 위치로부터의 거리는 각각 $5,4$입니다. 관광지 $5$가 비타로에게서 가장 가까운 관광지이므로, 비타로는 좌표 $5$에서 좌표 $9$로 이동하여 관광지 $5$를 방문합니다.
5. 아직 방문하지 않은 관광지는 $1$입니다. 관광지 $1$이 비타로에게서 가장 가까운 관광지이므로, 비타로는 좌표 $9$에서 좌표 $0$으로 이동하여 관광지 $1$을 방문합니다.

비타로의 총 이동 거리는 $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$의 제한을 만족합니다.