ในเมือง JOI มีถนนที่ยาวมาก ซึ่งสามารถมองเป็นเส้นจำนวนจริงได้ ตำแหน่งบนถนนแทนด้วยพิกัดที่เป็นจำนวนจริง ในเมือง JOI มีสถานที่ท่องเที่ยว $N$ แห่งอยู่ตามถนน หมายเลขตั้งแต่ $1$ ถึง $N$ ตามลำดับพิกัดจากน้อยไปมาก พิกัดของสถานที่ท่องเที่ยวแห่งที่ $i$ ($1\le i\le N$) คือ $X_i$

Bitaro จะไปเยี่ยมชมสถานที่ท่องเที่ยวทุกแห่งในเมือง JOI เนื่องจากคติประจำใจของเขาคือ “โลภ” เขาจึงจะทำขั้นตอนต่อไปนี้ซ้ำจนกว่าจะเยี่ยมชมครบทุกแห่ง

• ให้ $x$ เป็นพิกัดปัจจุบันของ Bitaro จากสถานที่ท่องเที่ยวที่ยังไม่ได้เยี่ยมชม เลือกแห่งที่ $i$ ซึ่งมีระยะห่าง $|x-X_i|$ จากตำแหน่งปัจจุบันของ Bitaro น้อยที่สุด จากนั้น Bitaro จะเคลื่อนที่ไปยังตำแหน่งของสถานที่แห่งที่ $i$ และเยี่ยมชมที่นั่น หากมีหลายแห่งที่มีระยะห่างน้อยที่สุดเท่ากัน เขาจะไปยังแห่งที่มีพิกัดน้อยที่สุด ในที่นี้ $|t|$ หมายถึงค่าสัมบูรณ์ของ $t$

อย่างไรก็ตาม ด้วยประสบการณ์หลายปี Bitaro รู้ว่าหากเคลื่อนที่ตามขั้นตอนข้างต้นซ้ำ ๆ ระยะทางรวมอาจยาวกว่าที่คาดไว้ เนื่องจากระยะทางรวมเปลี่ยนไปตามพิกัดเริ่มต้น เขาจึงต้องการทราบระยะทางรวมจนกว่าจะเยี่ยมชมครบทุกแห่ง เมื่อเริ่มจากพิกัดเริ่มต้นที่เป็นตัวเลือกแต่ละค่าจาก $Q$ ค่า ได้แก่ $S_1,S_2,\ldots,S_Q$

เพื่อช่วย Bitaro จงเขียนโปรแกรมที่รับข้อมูลของเมือง JOI และตัวเลือกพิกัดเริ่มต้น แล้วคำนวณระยะทางรวมเมื่อเริ่มจากพิกัดเริ่มต้นแต่ละค่า

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

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

ข้อมูลส่งออก

เขียนข้อมูล $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$ ซึ่งมีระยะห่างจากตำแหน่งปัจจุบันของเขาเป็น $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$

เนื่องจากระยะทางรวมของ 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$