题目描述

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 \dots 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\sim 3$：$N\leq 5000$。
• 测试点 $4\sim 7$：对于所有 $i$ 有 $a_i\leq 10$。
• 测试点 $8\sim 11$：没有标号出现超过 $10$ 次。
• 测试点 $12\sim 20$：没有额外限制。