题目描述

众所周知，Sam 很喜欢吃羊腿，喜欢到自己开了一家羊腿店。

最近快放假了，于是他准备搞一个促销活动。

Sam 拿出了自己珍藏的 "$super$ 无敌 $plus$ $pro$ $max$ 大羊腿" 准备切成几份出售。

由于羊腿的每个部位价值不同，并且这条羊腿特别特别特别长，于是 Sam 准备先将它从左向右划分成 $n$ 个区域，依次编号为 $1 \sim n$，其中第 $i$ 个区域的价值为 $a_i$。

现在 Sam 准备将羊腿切割成几份出售，但是由于要切割后出售，肯定不能将很多种不同价值的区域留在同一块羊腿里出售。

于是 Sam 决定设置一个羊腿差异度 $k$。

如果切下一段羊腿 $a_l \sim a_r$ 中价值的种数 $\leq k$，那么这一段羊腿就被 Sam 认为是合格的，否则就是不合格的。

而这条羊腿是 Sam 珍藏已久的，每一次切割都仿佛切在了 Sam 的心上，所以 Sam 希望知道在设定 $k$ 的情况下，最少需要将羊腿切几次？

输入格式

输入第一行包含一个正整数 $n$ 表示区域数量。

输入第二行包含 $n$ 个整数 $a_i$ 分别表示羊腿每个区域的价值。

输出格式

依次输出 $n$ 个整数，分别表示 $k = 1,2,3 \dots n$ 时的答案。

数据范围

对于前 $10\%$ 的数据，$a_i\leq 2$；

对于前 $20\%$ 的数据，$a_i\leq 10$；

对于前 $40\%$ 的数据，$n\leq 1000$；

对于前 $80\%$ 的数据，$n\leq 5\times 10^4$；

对于 $100\%$ 的数据，$1\leq n\leq 10^5,1\leq a_i\leq n$。

样例输入

6
1 1 2 3 1 2

样例输出

4 2 0 0 0 0

样例解释

对于 $k = 1$ 时，切割后的区域为 $[1,1],[2],[3],[1],[2]$。 对于 $k = 2$ 时，切割后的区域为 $[1,1,2],[3,1],[2]$。 对于 $k >=3$ 时，不用切。