يوجد في مدينة 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{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\le200\,000$.
• $1\le Q\le200\,000$.
• $0\le X_i\le10^9$ ($1\le i\le N$).
• $X_i<X_{i+1}$ ($1\le i\le N-1$).
• $0\le S_j\le10^9$ ($1\le j\le Q$).
• جميع القيم المعطاة أعداد صحيحة.

المهام الفرعية

1. (5 نقاط) $Q=1$، $N\le2\,000$.
2. (10 نقاط) $Q=1$.
3. (30 نقطة) $X_{i+1}-X_i\le100$ ($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.