瑞克和莫蒂想要找到先生。 PBH 他们无法单独做到这一点。所以他们需要米塞克斯先生。他们产生了 n 个 Meeseek 先生,排成一排,编号从 1 到 n。他们每个人都有自己的颜色。第 i 个 Meeseeks 先生的颜色是 ai。
瑞克和莫蒂正在集结他们的军队,他们想将米塞克斯先生分成几个小队。他们不希望自己的小队颜色太丰富,因此每个小队应该有最多 k 种不同颜色的 Meeseeks 先生。此外,每个小队都应该是队列中 Meeseeks 先生的连续子阵列。这意味着对于每个 1 ≤ i ≤ e ≤ j ≤ n,如果 Mr. Meeseeks 号码 i 和 Mr. Meeseeks 号码 j 在同一个小队中,那么 Mr. Meeseeks 号码 e 应该在同一个小队中。
另外,每个小队都需要自己的要塞,而建造要塞需要资金,所以他们希望小队的总数最小化。
Rick 和 Morty 尚未最终确定 k 的准确值,因此为了选择它,对于 1 到 n(含)之间的每个 k 需要知道所需的最小 presidios 数量。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 105) — Mr. Meeseeks 的数量。
第二行包含 n 个整数 a1,a2,...,一个以空格分隔的 (1 ≤ ai ≤ n) — Meeseeks 先生的颜色(按排成一行的顺序排列)。
输出
在输入的第一行也是唯一一行中打印 n 个由空格分隔的整数。如果 k 的值为 i,则第 i 个整数应该是所需的最小 presidios 数。
示例
输入 #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
注意
对于第一个示例测试用例,针对每个 k 将军队划分为小队的一些最佳方法是:
1. [1], [3], [4], [3, 3]
2. [1], [3, 4, 3, 3]
3. [1, 3, 4, 3, 3]
4. [1, 3, 4, 3, 3]
5. [1, 3, 4, 3, 3]
对于第二个测试用例,为每个 k 将军队划分为小队的一些最佳方法是:
1. [1], [5], [7], [8], [1], [7], [6], [1]
2. [1, 5], [7, 8], [1, 7], [6, 1]
3. [1, 5, 7], [8], [1, 7, 6, 1]
4. [1, 5, 7, 8], [1, 7, 6, 1]
5. [1, 5, 7, 8, 1, 7, 6, 1]
6. [1, 5, 7, 8, 1, 7, 6, 1]
7. [1, 5, 7, 8, 1, 7, 6, 1]
8. [1, 5, 7, 8, 1, 7, 6, 1]