Рухомі точки#230
Дано крапок, розташованих на вісі , -та з яких має координату x_i. Ви можете рухати крапки. Крім того, ви знаєте, що крапки настільки малі, що якщо вони перетинаються, вони зливаються в одну крапку. Коли дві крапки зливаються, крапка з меншим індексом перекриває крапку з більшим, тому її індекс буде дорівнювати найменшому індексу серед їх індексів. За одну секунду ви можете зробити наступне:
Виберіть одну крапку серед всіх наявних крапок. Позначимо її індекс як .
Перемістіть крапку з індексом з позиції x_j на (x_j-1) або на (x_j+1).
Іншими словами, за одну секунду ви можете вибрати крапку та перемістити її ліворуч або праворуч на .
Дано запитів. Для кожного запиту вам потрібно вивести найменшу кількість крапок, які можуть залишитися на вісі після того, як пройшло секунд.
Перший рядок містить одне ціле число (1 \le n \le 2 \cdot 10^5) — кількість крапок.
Другий рядок містить цілих чисел x_i (-10^6 \le x_i \le 10^6) — координати крапок на лінії.
Наступний рядок містить одне ціле число (1 \le q \le 2 \cdot 10^5) — кількість запитів.
Наступний рядок містить цілих чисел t_i (0 \le t_i \le 10^{9}).
Виведіть рядків — відповіді на відповідні запити.
Приклад 1
Приклад 2
( балів): n \le 3;
( балів): 0 \le x_i \le 20;
( балів): t_i \le 20;
( балів): n,q \le 3000;
( балів): q \le 100;
( бали): без додаткових обмежень.