Cowdependence

문제

Farmer John's $NN$ $(1\le N\le {10}^5)(1\; \backslash leq\; N\; \backslash leq\; 10^5)$ cows have been arranged into a line. The $ii$th cow has label $a_{i}a\_i$ ($1\le a_i\le N1\; \backslash leq\; a\_i\; \backslash leq\; N$). A group of cows can form a friendship group if they all have the same label and each cow is within $xx$ cows of all the others in the group, where $xx$ is an integer in the range $[1,N][1,N]$. Every cow must be in exactly one friendship group.

For each $xx$ from $11$ to $NN$, calculate the minimum number of friendship groups that could have formed.

입력

The first line consists of an integer $NN$.

The next line contains $a_1\mathrm{.}\mathrm{.}\mathrm{.}{a}_{N}a\_1\; ...\; a\_N$, the labels of each cow.

출력

For each $xx$ from $11$ to $NN$, output the minimum number of friendship groups for that $xx$ on a new line.

힌트

Here are examples of how to assign cows to friendship groups for $x=1x=1$ and $x=2x=2$ in a way that minimizes the number of groups. Each letter corresponds to a different group.

Example:

       1 1 1 9 2 1 2 1 1
x = 1: A B B C D E F G G (7 groups)
x = 1: A A B C D E F G G (7 groups, alternative grouping)
x = 2: A A A B C D C E E (5 groups)
x = 2: A A A B C D C D E (5 groups, alternative grouping)

9
1 1 1 9 2 1 2 1 1

7
5
4
4
4
4
4
3
3