Till I Collapse

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

Rick 和 Morty 生成了 $n$ 个排成一行的 Mr. Meeseeks，编号为 $1$ 到 $n$。第 $i$ 个 Mr. Meeseeks 的颜色为 $a_i$。

他们要把整条队列划分成若干个非空连续段。对于给定的整数 $k$，每一段中不同颜色的数量都不能超过 $k$。每一段都需要建造一个据点，因此他们希望划分出的段数尽量少。

请对每个 $k=1,2,\ldots,n$，分别求出最少需要划分成多少段。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各位置的颜色。

输出格式

输出一行 $n$ 个整数。第 $k$ 个整数表示每段至多包含 $k$ 种不同颜色时，覆盖整个序列所需的最少段数。

样例输入 1

5
1 3 4 3 3

样例输出 1

4 2 1 1 1

样例输入 2

8
1 5 7 8 1 7 6 1

样例输出 2

8 4 3 2 1 1 1 1

数据范围

对于全部数据，$1\le n\le 10^5$，$1\le a_i\le n$。