Сборище друзей

У Сакурако есть $n$ друзей. Каждый из них может быть описан своим вкладом на сайте по соревновательному программированию CodeCoders. Друг $i$ описывается числом $a_i$ — его вкладом.

Прямо сейчас, среди этих $n$ друзей, друг $i$ знаком с другом $j$ тогда и только тогда, когда $|a_i-a_j|<k$. Сакурако хочет собрать как можно больше людей на вечеринку. Однако он хочет, чтобы все они были незнакомы друг с другом.

Формально, если он решит пригласить набор людей $\mathcal{S}=\{x_1,x_2,\dots ,x_m\}$, то для каждого $i,j\in \mathcal{S}$, где $i\ne j$, должно выполняться условие $|a_{x_i}-a_{x_j}|\ge k$.

Из всех возможных наборов людей он хочет узнать размер самого большого.

К сожалению, Сакурако не знает значение $k$, поэтому ему нужно вычислить ответ для каждого $k$ $(1\le k\le n)$.

Входные данные

Первая строка содержит одно целое число $n$ ($1\le n\le 10^6$) — количество друзей Сакурако.

Вторая строка содержит $n$ целых чисел $a_1,\dots ,a_n$ ($-5\cdot 10^5\le a_i\le 5\cdot 10^5$) — вклад каждого друга.

Выходные данные

Выведите $n$ чисел. $i$-е число обозначает максимальный размер набора $\mathcal{S}$ для $k=i$.

Примеры

Примечание

В первом тесте:

• Когда $k=1$, $\mathcal{S}=\{1,2,3,4,6\}$;

• Для $k=2$ можно доказать, что максимальное возможное $\mathcal{S}$ это $\mathcal{S}=\{1,3,4,6\}$;

• Для $k=3$, $k=4$ и $k=5$ можно доказать, что одно из максимальных возможных $\mathcal{S}$ это $\mathcal{S}=\{3,4,6\}$;

• Для $k=6$ можно доказать, что одно из максимальных возможных $\mathcal{S}$ это $\mathcal{S}=\{1,4\}$.

Оценивание

1. ($6$ баллов): $a_i=a_{i-1}+1$ для всех $2\le i\le n$;

2. ($14$ баллов): $-10\le a_i\le 10$;

3. ($41$ балл): $n\le 1000$;

4. ($77$ баллов): $-30\le a_i\le 30$;

5. ($112$ баллов): без дополнительных ограничений.