样例下载

题目描述

N 个罪犯站在数轴上，第 i 个罪犯的坐标恰好也为 i。每个罪犯有一个编号，第 i 个罪犯的编号为 $A_i$。

如果若干个罪犯编号相同，并且他们中的任意两个罪犯的距离都不超过 d，那么这些罪犯就有可能属于同一个犯罪团伙。

已知一个罪犯属于且仅属于一个犯罪团伙。

问：当 d = 1, 2, ……, N 时，最少可能存在多少个犯罪团伙？

输入格式

第一行：一个整数 $N$。

第二行：$N$ 个整数 $A_i$

输出格式

共 N 行，每行一个整数，依次表示当 d = 1, 2, ……, N 时的答案。

输入样例

9
1 1 1 9 2 1 2 1 1

输出样例

7
5
4
4
4
4
4
3
3

样例解释

下面例子中，假设每个大写字母代表一个团伙。

$d=1$：

       1 1 1 9 2 1 2 1 1
d = 1: A B B C D E F G G（7 个团伙）
d = 1: A A B C D E F G G（7 个团伙，另一种方案）

$d=2$:

       1 1 1 9 2 1 2 1 1
d = 2: A A A B C D C E E（5 个团伙）
d = 2: A A A B C D C D E（5 个团伙，另一种方案）

其他略。

数据范围

100% 的数据：$1 ≤ N ≤ 10^5$, $1 ≤ A_i ≤ N$. 其中

• 10% 的数据：$N≤ 5000$。
• 20% 的数据：对于所有 $i$ 有 $A_i ≤ 10$。
• 20% 的数据：没有一个编号出现超过 $10$ 次。