06748. USACO·牛群依赖关系 未做

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

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

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

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

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

【样例解释】

• 测试点 4-7：对于所有 $i$ 有 $a_i\le 10$。

• 测试点 8-11：没有标号出现超过 $10$ 次。

• 测试点 12-20：没有额外限制。

【数据规模与约定】

• 测试点 2-3：$N\le 5000$。

• 测试点 4-7：对于所有 $i$ 有 $a_i\le 10$。

• 测试点 8-11：没有标号出现超过 $10$ 次。

• 测试点 12-20：没有额外限制。

供题：Chongtian Ma