Зустріч на вечірці

Сакурако має $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$ балів): без додаткових обмежень.