JOI қаласында нақты сандар түзуі ретінде қарастыруға болатын өте ұзын жол бар. Жол бойындағы орын нақты сандық координатамен сипатталады. JOI қаласында жол бойында координаталарының өсу ретімен $1$-ден $N$-ге дейін нөмірленген $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$ ішкі есептерінің шектеулерін қанағаттандырады.