Problem 1. Cowdependence

USACO 2024 December Contest, Gold

Farmer John 的 $N$（$1 \leq N \leq 10^5$）头奶牛已经排成一行。第 $i$ 头奶牛的标号是 $a_i$（$1 \leq a_i \leq N$）。一群奶牛可以组成一个友好小组，如果她们都具有相同的标号，并且每头奶牛都在小组中的其他所有奶牛的 $x$ 头奶牛距离范围内，其中 $x$ 是范围 $[1,N]$ 内的一个整数。每头奶牛必须属于恰好一个友好小组。

对于从 $1$ 到 $N$ 的每一个 $x$，计算可能组成的友谊小组的最小数量。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含一个整数 $N$。

下一行包含 $a_1 ... a_N$，为每头奶牛的标号。

输出格式（输出至终端 / 标准输出）：

对于从 $1$ 到 $N$ 的每一个 $x$ 输出一行，包含该 $x$ 所对应的友谊小组的最小数量。

输入样例：

9
1 1 1 9 2 1 2 1 1

输出样例：

7
5
4
4
4
4
4
3
3

以下为当 $x=1$ 和 $x=2$ 时将奶牛以最小化小组数量的方式组成友谊小组的一些例子。每个字母对应一个不同的小组。

例：

       1 1 1 9 2 1 2 1 1
x = 1: A B B C D E F G G（7 组）
x = 1: A A B C D E F G G（7 组，另一种分组方案）
x = 2: A A A B C D C E E（5 组）
x = 2: A A A B C D C D E（5 组，另一种分组方案）

测试点性质： 测试点 2-3：$N\le 5000$。测试点 4-7：对于所有 $i$ 有 $a_i\le 10$。测试点 8-11：没有标号出现超过 $10$ 次。测试点 12-20：没有额外限制。

供题：Chongtian Ma