Minimum Friendly Group Partitioning

Farmer John's N cows (\(1 \le N \le 10^5\)) are lined up. The i-th cow has an identifier \(a_i\) (\(1 \le a_i \le N\)). A set of cows can form a friendly group if they all share the same identifier and, for a given integer \(x\) (\(1 \le x \le N\)), every pair of cows in the group is within \(x\) positions of each other; that is, if two cows in the group appear at positions \(i\) and \(j\) in the line then \(|i - j| \le x\). Moreover, each cow must belong to exactly one friendly group.

For each \(x\) from 1 to \(N\), determine the minimum number of friendly groups the cows can be partitioned into.

inputFormat

The first line contains a single integer \(N\), the number of cows.

The second line contains \(N\) integers \(a_1, a_2, \ldots, a_N\) representing the identifiers of the cows in their order.

outputFormat

Output \(N\) integers separated by spaces. The \(i\)th integer is the minimum number of friendly groups for \(x = i\).

sample

5
1 1 1 1 1

3 2 2 1 1