CF786C.Till I Collapse

Rick and Morty want to find MR. PBH and they can't do it alone. So they need of Mr. Meeseeks. They Have generated n Mr. Meeseeks, standing in a line numbered from 1 to n. Each of them has his own color. i-th Mr. Meeseeks' color is a__i.

Rick and Morty are gathering their army and they want to divide Mr. Meeseeks into some squads. They don't want their squads to be too colorful, so each squad should have Mr. Meeseeks of at most k different colors. Also each squad should be a continuous subarray of Mr. Meeseeks in the line. Meaning that for each 1 ≤ i ≤ e ≤ j ≤ n, if Mr. Meeseeks number i and Mr. Meeseeks number j are in the same squad then Mr. Meeseeks number e should be in that same squad.

Also, each squad needs its own presidio, and building a presidio needs money, so they want the total number of squads to be minimized.

Rick and Morty haven't finalized the exact value of k, so in order to choose it, for each k between 1 and n (inclusive) need to know the minimum number of presidios needed.

瑞克和莫蒂想要找到PBH先生，但他们无法独自完成这项任务，因此需要梅西克斯先生的帮助。他们生成了 $n$ 个梅西克斯先生，排成一列，编号从 $1$ 到 $n$。每个梅西克斯先生都有自己的颜色，其中第 $i$ 个梅西克斯先生的颜色为 $a_i$。

瑞克和莫蒂正在集结他们的军队，希望将梅西克斯先生划分为若干小队。他们不希望小队过于“多彩”，因此每个小队中最多只能包含 $k$ 种不同的颜色。此外，每个小队必须是梅西克斯先生队列中的一个连续子数组。也就是说，对任意满足 $1 \le i \le e \le j \le n$ 的下标，若第 $i$ 号与第 $j$ 号梅西克斯先生属于同一小队，则第 $e$ 号梅西克斯先生也必须属于该小队。

此外，每个小队都需要一座专属的“总统府”（presidio），而建造总统府需要花费资金，因此他们希望小队总数尽可能少。

瑞克和莫蒂尚未最终确定 $k$ 的具体取值；为了选定合适的 $k$，他们需要对每个 $k$（$k$ 取 $1$ 到 $n$ 之间的所有整数，含端点）计算出所需的最少总统府数量。

The first line of input contains a single integer n (1 ≤ n ≤ 105) — number of Mr. Meeseeks.

The second line contains n integers _a_1, _a_2, ..., a__n separated by spaces (1 ≤ a__i ≤ n) — colors of Mr. Meeseeks in order they standing in a line.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— Mr. Meeseeks 的数量。

第二行包含 $n$ 个由空格分隔的整数 $a_1,\,a_2,\,...,\,a_n$（$1 \leq a_i \leq n$）—— 按照 Mr. Meeseeks 在队伍中站立的顺序给出的颜色。

In the first and only line of input print n integers separated by spaces. i-th integer should be the minimum number of presidios needed if the value of k is i.

在输入的第一行且唯一一行中，输出 n 个由空格分隔的整数。其中第 i 个整数表示当 k 的值为 i 时所需的最少哨所数量。

For the first sample testcase, some optimal ways of dividing army into squads for each k are:

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]

For the second testcase, some optimal ways of dividing army into squads for each k are:

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]

对于第一个样例测试用例，每个 $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]$