Cowdependence

Time limit2sMemory limit2048 MB

Summary

For each x from 1 to N, find the fewest groups of same-label cows where every two cows in a group are at most x positions apart.

Level: Medium7 of 10
Topics: Greedy, Hash map, Array
Solved: No attempts yet

Problem

Farmer John has $N$ $(1 \leq N \leq 10^5)$ cows arranged in a line. The $i$ th cow has label $a_i$ ( $1 \leq a_i \leq N$ ). A group of cows can form a friendship group if all cows in the group have the same label and each cow is within $x$ cows of every other cow in the group, where $x$ is an integer in the range $[1, N]$ . Every cow must belong to exactly one friendship group.

For each $x$ from $1$ to $N$ , compute the minimum number of friendship groups that can be formed.

Input

The first line contains an integer $N$ .

The next line contains the labels $a_1, \dots, a_N$ of the cows.

Output

For each $x$ from $1$ to $N$ , output the minimum number of friendship groups for that $x$ on a new line.

Hint

In the sample, the labels $1, 1, 1, 9, 2, 1, 2, 1, 1$ need 7 groups when $x=1$ and 5 groups when $x=2$ .

Examples1

Example 1
Input
```
9
1 1 1 9 2 1 2 1 1
```
Expected output
```
7
5
4
4
4
4
4
3
3
```