Di Kota JOI terdapat jalan yang sangat panjang, yang dapat dianggap sebagai garis bilangan real. Posisi di jalan tersebut dinyatakan dengan koordinat bilangan real. Di Kota JOI terdapat $N$ tempat wisata di sepanjang jalan, yang diberi nomor dari $1$ sampai $N$ menurut urutan koordinat yang meningkat. Koordinat tempat wisata ke-$i$ ($1\le i\le N$) adalah $X_i$.

Bitaro akan mengunjungi semua tempat wisata di Kota JOI. Karena «rakus» adalah semboyan hidupnya, ia akan mengulangi prosedur berikut sampai semua tempat wisata telah dikunjungi.

• Misalkan $x$ adalah koordinat Bitaro saat ini. Di antara tempat wisata yang belum dikunjunginya, pilih tempat wisata $i$ dengan jarak $|x-X_i|$ dari posisi Bitaro saat ini yang paling kecil. Lalu Bitaro bergerak ke posisi tempat wisata $i$ dan mengunjunginya. Jika ada lebih dari satu tempat wisata seperti itu, ia bergerak ke tempat wisata dengan koordinat paling kecil di antara semuanya. Di sini, $|t|$ adalah nilai mutlak dari $t$.

Namun, berkat pengalamannya selama bertahun-tahun, Bitaro mengetahui bahwa jika ia bergerak dengan mengulangi prosedur di atas, total jarak tempuhnya mungkin lebih panjang dari yang ia perkirakan. Karena total jarak tempuh berubah sesuai koordinat awal, ia ingin mengetahui total jarak tempuh sampai semua tempat wisata dikunjungi jika ia mulai dari masing-masing dari $Q$ kandidat koordinat awal $S_1,S_2,\ldots,S_Q$.

Untuk membantu Bitaro, tulislah program yang menghitung total jarak tempuh jika ia mulai dari setiap kandidat koordinat awal, berdasarkan informasi Kota JOI dan kandidat koordinat awal yang diberikan.

Masukan

Baca data berikut dari masukan standar.

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

Keluaran

Tuliskan $Q$ baris ke keluaran standar. Baris ke-$j$ ($1\le j\le Q$) harus berisi total jarak tempuh jika Bitaro mulai dari koordinat $S_j$.

Batasan

• $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$).
• Semua nilai yang diberikan adalah bilangan bulat.

Subsoal

1. (5 poin) $Q=1$, $N\le 2\,000$.
2. (10 poin) $Q=1$.
3. (30 poin) $X_{i+1}-X_i\le 100$ ($1\le i\le N-1$).
4. (55 poin) Tidak ada batasan tambahan.

Contoh

Masukan 1

5
0 5 6 7 9
1
7

Keluaran 1

15

Penjelasan

Jika Bitaro mulai dari koordinat $7$, ia mengunjungi semua tempat wisata sebagai berikut.

1. Ia belum mengunjungi tempat wisata $1,2,3,4,5$, yang jaraknya dari posisi Bitaro saat ini berturut-turut adalah $7,2,1,0,2$. Karena tempat wisata $4$ adalah yang paling dekat dari Bitaro, ia tetap di koordinat $7$ dan mengunjungi tempat wisata $4$.
2. Ia belum mengunjungi tempat wisata $1,2,3,5$, yang jaraknya dari posisi Bitaro saat ini berturut-turut adalah $7,2,1,2$. Karena tempat wisata $3$ adalah yang paling dekat dari Bitaro, ia bergerak dari koordinat $7$ ke koordinat $6$ dan mengunjungi tempat wisata $3$.
3. Ia belum mengunjungi tempat wisata $1,2,5$, yang jaraknya dari posisi Bitaro saat ini berturut-turut adalah $6,1,3$. Karena tempat wisata $2$ adalah yang paling dekat dari Bitaro, ia bergerak dari koordinat $6$ ke koordinat $5$ dan mengunjungi tempat wisata $2$.
4. Ia belum mengunjungi tempat wisata $1,5$, yang jaraknya dari posisi Bitaro saat ini berturut-turut adalah $5,4$. Karena tempat wisata $5$ adalah yang paling dekat dari Bitaro, ia bergerak dari koordinat $5$ ke koordinat $9$ dan mengunjungi tempat wisata $5$.
5. Ia belum mengunjungi tempat wisata $1$. Karena tempat wisata $1$ adalah yang paling dekat dari Bitaro, ia bergerak dari koordinat $9$ ke koordinat $0$ dan mengunjungi tempat wisata $1$.

Karena total jarak tempuh Bitaro adalah $15$, keluarkan 15.

Contoh masukan ini memenuhi batasan semua subsoal.

Masukan 2

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

Keluaran 2

9
10
11
12
13
14
15
16
17
9

Penjelasan

Contoh masukan ini memenuhi batasan Subsoal 3, 4.