Рухомі точки

Дано $n$ крапок, розташованих на вісі $X$, $i$-та з яких має координату $x_i$. Ви можете рухати крапки. Крім того, ви знаєте, що крапки настільки малі, що якщо вони перетинаються, вони зливаються в одну крапку. Коли дві крапки зливаються, крапка з меншим індексом перекриває крапку з більшим, тому її індекс буде дорівнювати найменшому індексу серед їх індексів. За одну секунду ви можете зробити наступне:

1. Виберіть одну крапку серед всіх наявних крапок. Позначимо її індекс як $j$.

2. Перемістіть крапку з індексом $j$ з позиції $x_j$ на $(x_j-1)$ або на $(x_j+1)$.

Іншими словами, за одну секунду ви можете вибрати крапку та перемістити її ліворуч або праворуч на $1$.

Дано $q$ запитів. Для кожного запиту вам потрібно вивести найменшу кількість крапок, які можуть залишитися на вісі після того, як пройшло $t$ секунд.

Вхідні дані

Перший рядок містить одне ціле число $n$ ($1\le n\le 2\cdot 10^5$) — кількість крапок.

Другий рядок містить $n$ цілих чисел $x_i$ ($-10^6\le x_i\le 10^6$) — координати крапок на лінії.

Наступний рядок містить одне ціле число $q$ ($1\le q\le 2\cdot 10^5$) — кількість запитів.

Наступний рядок містить $q$ цілих чисел $t_i$ ($0\le t_i\le 10^9$).

Вихідні дані

Виведіть $q$ рядків — відповіді на відповідні запити.

Приклади

Оцінювання

1. ($11$ балів): $n\le 3$;

2. ($16$ балів): $0\le x_i\le 20$;

3. ($14$ балів): $t_i\le 20$;

4. ($17$ балів): $n,q\le 3000$;

5. ($18$ балів): $q\le 100$;

6. ($24$ бали): без додаткових обмежень.