Party gathering

Sakurako has $n$ friends. Each of them can be described by their contribution on the competitive programming web-page CodeCoders. Friend $i$ is described by a number $a_i$ — his contribution.

Right now, within these $n$ friends, friend $i$ is familiar with friend $j$ if and only if $|a_i-a_j|<k$. Sakurako wants to gather as many people as possible to the party. However, he wants for all of them to be unfamiliar with each other.

Formally, if he chose to invite a set of people $\mathcal{S}=\{x_1,x_2,\dots ,x_m\}$, then for every $i,j\in \mathcal{S}$ where $i\ne j$, the condition $|a_{x_i}-a_{x_j}|\ge k$ must be fulfilled.

Out of all possible sets of people, he wants to know the size of the largest one.

Unfortunately, Sakurako doesn't know the value of $k$, so he has to compute the answer for each $k$ $(1\le k\le n)$.

Input

The first line contains one integer $n$ ($1\le n\le 10^6$) — the amount of Sakurako's friends.

The second line contains $n$ integers $a_1,\dots ,a_n$ ($-5\cdot 10^5\le a_i\le 5\cdot 10^5$) — the contribution of each friend.

Output

Output $n$ numbers. The $i$-th number denotes the largest size of set $\mathcal{S}$ for $k=i$.

Examples

Note

In the first test:

• When $k=1$, $\mathcal{S}=\{1,2,3,4,6\}$;

• For $k=2$, it can be proven that the largest possible $\mathcal{S}$ is $\mathcal{S}=\{1,3,4,6\}$;

• For $k=3$, $k=4$, and $k=5$, it can be proven that one of the largest possible $\mathcal{S}$ is $\mathcal{S}=\{3,4,6\}$;

• For $k=6$, it can be proven that one of the largest $\mathcal{S}$ is $\mathcal{S}=\{1,4\}$.

Scoring

1. ($6$ points): $a_i=a_{i-1}+1$ for all $2\le i\le n$;

2. ($14$ points): $-10\le a_i\le 10$;

3. ($41$ points): $n\le 1000$;

4. ($77$ points): $-30\le a_i\le 30$;

5. ($112$ points): without additional restrictions.