ב־JOI City יש כביש ארוך מאוד, שאפשר לראות בו את ישר המספרים הממשיים. מיקום על הכביש מיוצג באמצעות קואורדינטה ממשית. לאורך הכביש יש $N$ אתרי תיירות, הממוספרים מ־$1$ עד $N$ בסדר קואורדינטות עולה. הקואורדינטה של אתר התיירות ה־$i$ ($1 \le i \le N$) היא $X_i$.

Bitaro מתכוון לבקר בכל אתרי התיירות ב־JOI City. מכיוון ש״חמדנות״ היא סיסמת חייו, הוא יחזור על התהליך הבא עד שיבקר בכל האתרים.

• נסמן ב־$x$ את הקואורדינטה הנוכחית של Bitaro. מבין אתרי התיירות שטרם ביקר בהם, נבחר את האתר $i$ שהמרחק $|x-X_i|$ ממיקומו הנוכחי של Bitaro אליו הוא הקטן ביותר. לאחר מכן Bitaro עובר למיקומו של האתר $i$ ומבקר בו. אם יש כמה אתרים כאלה, הוא עובר לאתר שהקואורדינטה שלו היא הקטנה ביותר. כאן $|t|$ הוא הערך המוחלט של $t$.

אולם בזכות ניסיון רב שנים, Bitaro יודע שאם ינוע לפי התהליך הזה, המרחק הכולל שיעבור עלול להיות גדול מהצפוי. מכיוון שהמרחק הכולל משתנה לפי קואורדינטת ההתחלה, הוא רוצה לדעת את המרחק הכולל עד לביקור בכל האתרים כאשר הוא מתחיל בכל אחת מ־$Q$ קואורדינטות התחלה אפשריות $S_1,S_2,\ldots,S_Q$.

כדי לעזור ל־Bitaro, כתבו תוכנית אשר, בהינתן המידע על JOI City וקואורדינטות ההתחלה האפשריות, מחשבת את המרחק הכולל שיעבור אם יתחיל בכל אחת מהן.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי.

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

פלט

כתבו $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$ הוא הקרוב ביותר ל־Bitaro, הוא נשאר בקואורדינטה $7$ ומבקר באתר $4$.
2. הוא טרם ביקר באתרים $1,2,3,5$, והמרחקים ממיקומו הנוכחי אליהם הם $7,2,1,2$, בהתאמה. מכיוון שאתר $3$ הוא הקרוב ביותר ל־Bitaro, הוא עובר מהקואורדינטה $7$ לקואורדינטה $6$ ומבקר באתר $3$.
3. הוא טרם ביקר באתרים $1,2,5$, והמרחקים ממיקומו הנוכחי אליהם הם $6,1,3$, בהתאמה. מכיוון שאתר $2$ הוא הקרוב ביותר ל־Bitaro, הוא עובר מהקואורדינטה $6$ לקואורדינטה $5$ ומבקר באתר $2$.
4. הוא טרם ביקר באתרים $1,5$, והמרחקים ממיקומו הנוכחי אליהם הם $5,4$, בהתאמה. מכיוון שאתר $5$ הוא הקרוב ביותר ל־Bitaro, הוא עובר מהקואורדינטה $5$ לקואורדינטה $9$ ומבקר באתר $5$.
5. הוא טרם ביקר באתר $1$. מכיוון שאתר $1$ הוא הקרוב ביותר ל־Bitaro, הוא עובר מהקואורדינטה $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.