Зустріч на вечірці#11714
Сакурако має друзів. Кожного з них можна описати за їхнім внеском на веб-сторінці з олімпіадного програмування CodeCoders. Друг описується числом a_i — його внеском.
Зараз, серед цих друзів, друг знайомий з другом тоді й тільки тоді, коли |a_i-a_j| < k. Сакурако хоче зібрати як можна більше людей на вечірку. Однак він хоче, щоб усі вони були незнайомі один з одним.
Формально, якщо він вирішує запросити набір людей \mathcal{S} = \{x_1, x_2, \dots, x_m\}, то для кожного i, j \in \mathcal{S}, де i \neq j, повинна виконуватись умова |a_{x_i} - a_{x_j}| \ge k.
Серед усіх можливих наборів людей він хоче дізнатися розмір найбільшого з них.
На жаль, Сакурако не знає значення , тому йому потрібно обчислити відповідь для кожного (1 \le k \le n).
Перший рядок містить одне ціле число (1 \le n \le 10^6) — кількість друзів Сакурако.
Другий рядок містить цілих чисел a_1, \dots, a_n (-5 \cdot 10^5 \le a_i \le 5 \cdot 10^5) — внесок кожного друга.
Виведіть чисел. -те число позначає найбільший розмір набору для k = i.
Приклад
У першому тесті:
Коли k = 1, \mathcal{S} = \{1, 2, 3, 4, 6\};
Для k = 2, можна довести, що найбільший можливий — це \mathcal{S} = \{1, 3, 4, 6\};
Для k = 3, k = 4 та k = 5, можна довести, що один з найбільших можливих — це \mathcal{S} = \{3, 4, 6\};
Для k = 6, можна довести, що один з найбільших можливих — це \mathcal{S} = \{1, 4\}.
(6 балів): a_i = a_{i-1} + 1 для всіх 2 \le i \le n;
(14 балів): -10 \le a_i \le 10;
(41 бал): n \le 1000;
(77 балів): -30 \le a_i \le 30;
(112 балів): без додаткових обмежень.