{"problem":{"name":"E. 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":"CF787E"},"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 color. _i_\\-th Mr. Meeseeks' color is _a__i_.\n\nRick 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.\n\n<center>![image](https://espresso.codeforces.com/ddccfa4d4cd81e14f5522d6b4bd93043f50e0e84.png)</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.\n\nRick 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.\n\n## Input\n\nThe first line of input contains a single integer _n_ (1 ≤ _n_ ≤ 105) — number of Mr. Meeseeks.\n\nThe 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\n## Output\n\nIn 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\n[samples]\n\n## Note\n\nFor the first sample testcase, some optimal ways of dividing army into squads for each _k_ are:\n\n1.  \\[1\\], \\[3\\], \\[4\\], \\[3, 3\\]\n2.  \\[1\\], \\[3, 4, 3, 3\\]\n3.  \\[1, 3, 4, 3, 3\\]\n4.  \\[1, 3, 4, 3, 3\\]\n5.  \\[1, 3, 4, 3, 3\\]\n\nFor the second testcase, some optimal ways of dividing army into squads for each _k_ are:\n\n1.  \\[1\\], \\[5\\], \\[7\\], \\[8\\], \\[1\\], \\[7\\], \\[6\\], \\[1\\]\n2.  \\[1, 5\\], \\[7, 8\\], \\[1, 7\\], \\[6, 1\\]\n3.  \\[1, 5, 7\\], \\[8\\], \\[1, 7, 6, 1\\]\n4.  \\[1, 5, 7, 8\\], \\[1, 7, 6, 1\\]\n5.  \\[1, 5, 7, 8, 1, 7, 6, 1\\]\n6.  \\[1, 5, 7, 8, 1, 7, 6, 1\\]\n7.  \\[1, 5, 7, 8, 1, 7, 6, 1\\]\n8.  \\[1, 5, 7, 8, 1, 7, 6, 1\\]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"里克和莫蒂想找到PBH先生，但他们无法独自完成。因此他们需要梅瑟克先生。他们生成了 #cf_span[n] 个梅瑟克先生，排成一列，编号从 #cf_span[1] 到 #cf_span[n]。每个梅瑟克先生都有自己的颜色，第 #cf_span[i] 个梅瑟克先生的颜色是 #cf_span[ai]。\n\n里克和莫蒂正在集结他们的军队，他们希望将梅瑟克先生分成若干小队。他们不希望小队过于多彩，因此每个小队最多只能包含 #cf_span[k] 种不同颜色的梅瑟克先生。同时，每个小队必须是梅瑟克先生队列中的一个连续子数组。也就是说，对于任意 #cf_span[1 ≤ i ≤ e ≤ j ≤ n]，如果第 #cf_span[i] 个和第 #cf_span[j] 个梅瑟克先生在同一小队，则第 #cf_span[e] 个梅瑟克先生也必须在该小队中。\n\n此外，每个小队都需要自己的哨所，而建造哨所需要资金，因此他们希望小队的总数最小化。\n\n里克和莫蒂尚未确定 #cf_span[k] 的确切值，因此为了选择它，对于每个 #cf_span[k] 从 #cf_span[1] 到 #cf_span[n]（包含），都需要知道所需的最少哨所数量。\n\n输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）——梅瑟克先生的数量。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ n]）——按队列顺序排列的梅瑟克先生的颜色。\n\n在唯一的一行输出 #cf_span[n] 个用空格分隔的整数。第 #cf_span[i] 个整数应表示当 #cf_span[k] 的值为 #cf_span[i] 时所需的最少哨所数量。\n\n## Input\n\n输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）——梅瑟克先生的数量。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ n]）——按队列顺序排列的梅瑟克先生的颜色。\n\n## Output\n\n在唯一的一行输出 #cf_span[n] 个用空格分隔的整数。第 #cf_span[i] 个整数应表示当 #cf_span[k] 的值为 #cf_span[i] 时所需的最少哨所数量。\n\n[samples]\n\n## Note\n\n对于第一个测试用例，每个 #cf_span[k] 对应的最优分队方式如下：\n\n#cf_span[[1], [3], [4], [3, 3]]\n#cf_span[[1], [3, 4, 3, 3]]\n#cf_span[[1, 3, 4, 3, 3]]\n#cf_span[[1, 3, 4, 3, 3]]\n#cf_span[[1, 3, 4, 3, 3]]\n\n对于第二个测试用例，每个 #cf_span[k] 对应的最优分队方式如下：\n\n#cf_span[[1], [5], [7], [8], [1], [7], [6], [1]]\n#cf_span[[1, 5], [7, 8], [1, 7], [6, 1]]\n#cf_span[[1, 5, 7], [8], [1, 7, 6, 1]]\n#cf_span[[1, 5, 7, 8], [1, 7, 6, 1]]\n#cf_span[[1, 5, 7, 8, 1, 7, 6, 1]]\n#cf_span[[1, 5, 7, 8, 1, 7, 6, 1]]\n#cf_span[[1, 5, 7, 8, 1, 7, 6, 1]]\n#cf_span[[1, 5, 7, 8, 1, 7, 6, 1]]","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 $ i $-th Mr. Meeseeks.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq a_i \\leq n $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nFor each $ k \\in \\{1, 2, \\dots, n\\} $, compute $ f(k) $, the minimum number of contiguous non-overlapping squads (subarrays) into which $ A $ can be partitioned, such that each squad contains at most $ k $ distinct colors.  \n\nOutput: $ \\left( f(1), f(2), \\dots, f(n) \\right) $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF787E","tags":["data structures","trees"],"sample_group":[["5\n1 3 4 3 3","4 2 1 1 1"],["8\n1 5 7 8 1 7 6 1","8 4 3 2 1 1 1 1"]],"created_at":"2026-03-03 11:00:39"}}