English · Original
Chinese · Translation
Formal · Original
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.
<center></center>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.
## Input
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.
## Output
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_.
[samples]
## Note
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\]
Rick 和 Morty 想要找到 MR. PBH，但他们无法独自完成。因此他们需要 Mr. Meeseeks。他们生成了 #cf_span[n] 个 Mr. Meeseeks，排成一行，编号从 #cf_span[1] 到 #cf_span[n]。每个人都有自己的颜色，第 #cf_span[i] 个 Mr. Meeseeks 的颜色是 #cf_span[ai]。
Rick 和 Morty 正在集结军队，他们希望将 Mr. Meeseeks 分成若干个小队。他们不希望小队过于多彩，因此每个小队最多只能包含 #cf_span[k] 种不同颜色。此外，每个小队必须是 Mr. Meeseeks 序列中的一个连续子数组。也就是说，对于任意满足 #cf_span[1 ≤ i ≤ e ≤ j ≤ n] 的下标，如果第 #cf_span[i] 个和第 #cf_span[j] 个 Mr. Meeseeks 在同一小队中，则第 #cf_span[e] 个 Mr. Meeseeks 也必须在该小队中。
此外，每个小队都需要自己的监狱，而建造监狱需要花费金钱，因此他们希望最小化小队的总数。
Rick 和 Morty 尚未确定 #cf_span[k] 的确切值，因此为了选择它，对于每个 #cf_span[k]（从 #cf_span[1] 到 #cf_span[n]，包含两端），都需要知道所需的最少监狱数量。
输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）——Mr. Meeseeks 的数量。
第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ n]）——按排列顺序的 Mr. Meeseeks 的颜色。
在第一行且仅有的这一行中，输出 #cf_span[n] 个用空格分隔的整数。第 #cf_span[i] 个整数应表示当 #cf_span[k] 的值为 #cf_span[i] 时所需的最少监狱数量。
## Input
输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）——Mr. Meeseeks 的数量。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ n]）——按排列顺序的 Mr. Meeseeks 的颜色。
## Output
在第一行且仅有的这一行中，输出 #cf_span[n] 个用空格分隔的整数。第 #cf_span[i] 个整数应表示当 #cf_span[k] 的值为 #cf_span[i] 时所需的最少监狱数量。
[samples]
## Note
对于第一个测试用例，每个 #cf_span[k] 对应的军队划分最优方案如下：
#cf_span[[1], [3], [4], [3, 3]]
#cf_span[[1], [3, 4, 3, 3]]
#cf_span[[1, 3, 4, 3, 3]]
#cf_span[[1, 3, 4, 3, 3]]
#cf_span[[1, 3, 4, 3, 3]]
对于第二个测试用例，每个 #cf_span[k] 对应的军队划分最优方案如下：
#cf_span[[1], [5], [7], [8], [1], [7], [6], [1]]
#cf_span[[1, 5], [7, 8], [1, 7], [6, 1]]
#cf_span[[1, 5, 7], [8], [1, 7, 6, 1]]
#cf_span[[1, 5, 7, 8], [1, 7, 6, 1]]
#cf_span[[1, 5, 7, 8, 1, 7, 6, 1]]
#cf_span[[1, 5, 7, 8, 1, 7, 6, 1]]
#cf_span[[1, 5, 7, 8, 1, 7, 6, 1]]
#cf_span[[1, 5, 7, 8, 1, 7, 6, 1]]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of Mr. Meeseeks.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of colors, where $ a_i \in \{1, 2, \dots, n\} $ denotes the color of the $ i $-th Mr. Meeseeks.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq a_i \leq n $ for all $ i \in \{1, \dots, n\} $
**Objective**
For each $ k \in \{1, 2, \dots, n\} $, compute $ f(k) $, the minimum number of contiguous squads (subarrays) into which $ A $ can be partitioned such that each squad contains at most $ k $ distinct colors.
Output: $ f(1), f(2), \dots, f(n) $
API Response (JSON)
{
"problem": {
"name": "C. Till I Collapse",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF786C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Rick 和 Morty 想要找到 MR. PBH，但他们无法独自完成。因此他们需要 Mr. Meeseeks。他们生成了 #cf_span[n] 个 Mr. Meeseeks，排成一行，编号从 #cf_span[1] 到 #cf_span[n]。每个人都有自己的颜色，第 #cf_span[i] 个 Mr. Meeseeks 的颜色是 #cf_span[ai]。\n\nRick 和 Morty 正在集...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of Mr. Meeseeks. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of colors, where $ a_i \\in \\{1, 2, \\dots, n\\} $ denotes the color of the ...",
"is_translate": false,
"language": "Formal"
}
]
}