← 返回题目列表

Codeforces · 2141/F

F. 数组缩减

中文机器翻译题面 查看原题

给定一个数组 $$$a$$$,其中包含 $$$n$$$ 整数。

在一次操作中,您可以从此数组中选择一些元素并将其删除。但是,您选择的元素必须满足以下条件之一:

  • 要么所有选择的元素都相等;
  • 或者没有两个相同的选择元素。

请注意,如果您仅选择删除 $$$1$$$ 元素,它会自动满足这些条件。

例如,如果 $$$a = \{1, 2, 1, 1, 3\}$$$,则您可以在一次操作中删除的一些可能元素包括:

  • $$$1$$$-st 元素;
  • $$$1$$$-st 和 $$$3$$$-rd 元素;
  • 第 $$$1$$$-st、$$$3$$$-rd 和第 $$$4$$$-th 元素;
  • 第 $$$3$$$-rd 和第 $$$4$$$-th 元素;
  • 第$$$2$$$个、第$$$4$$$个和第$$$5$$$个元素;
  • 等等。

但是,您不能选择 $$$2$$$-nd、$$$3$$$-rd 和第 $$$4$$$-th 元素,因为 $$$2$$$-nd 元素不等于第 $$$4$$$-th,但 $$$3$$$-rd 元素等于第 $$$4$$$-th。

对于从 $$$0$$$ 到 $$$n - 1$$$ 的每个 $$$x$$$,您必须计算将数组大小减小到所需的最小操作数 正是 $$$x$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成:

  • 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 数组的大小;
  • 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — 数组本身。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$n$$$ 整数 $$$c_0, c_1, \dots, c_{n-1}$$$,其中 $$$c_i$$$ 是将数组大小精确减少到 $$$i$$$ 所需的最小操作数。

示例

输入
复制

5
11
5 5 5 5 2 2 2 8 6 1 7
6
3 3 3 3 3 3
5
2 1 3 5 4
8
1 1 1 2 3 4 5 6
1
1

输出
复制

3 3 2 2 2 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 
2 2 1 1 1 1 1 1 
1 

注意

在第一个例子中,可以得到答案如下:

  • $$$c_{0} = 3$$$:删除$$$a_{8}、a_{9}、a_{10}、a_{11}$$$;然后删除$$$a_{1}、a_{2}、a_{3}、a_{4}$$$;然后删除$$$a_{5}、a_{6}、a_{7}$$$;
  • $$$c_{1} = 3$$$:删除$$$a_{8}、a_{9}、a_{10}、a_{11}$$$;然后删除$$$a_{1}、a_{2}、a_{3}、a_{4}$$$;然后删除$$$a_{5},a_{6}$$$;
  • $$$c_{2} = 2$$$:删除$$$a_{7}、a_{8}、a_{9}、a_{10}、a_{11}$$$;然后删除$$$a_{1}、a_{2}、a_{3}、a_{4}$$$;
  • $$$c_{3} = 2$$$:删除$$$a_{7}、a_{8}、a_{9}、a_{10}、a_{11}$$$;然后删除$$$a_{1}、a_{2}、a_{3}$$$;
  • $$$c_{4} = 2$$$:删除$$$a_{7}、a_{8}、a_{9}、a_{10}、a_{11}$$$;然后删除 $$$a_{1}, a_{2}$$$;
  • $$$c_{5} = 1$$$:删除$$$a_{1}、a_{7}、a_{8}、a_{9}、a_{10}、a_{11}$$$;
  • $$$c_{6} = 1$$$:删除$$$a_{7}、a_{8}、a_{9}、a_{10}、a_{11}$$$;
  • $$$c_{7} = 1$$$:删除$$$a_{1}、a_{2}、a_{3}、a_{4}$$$;
  • $$$c_{8} = 1$$$: 删除$$$a_{1}, a_{2}, a_{3}$$$;
  • $$$c_{9} = 1$$$: 删除$$$a_{1}, a_{2}$$$;
  • $$$c_{10} = 1$$$: 删除$$$a_{7}$$$;