CF2141F.Array Reduction

给定一个包含 $n$ 个整数的数组 $a$。

每次操作，你可以选择数组中的若干元素并将它们移除。然而，你选择的元素必须满足以下两种条件之一：

• 所有被选择的元素都相等；
• 被选择的元素两两不同。

注意，如果只选择了 $1$ 个元素进行移除，则自动满足这些条件。

例如，如果 $a = \{1, 2, 1, 1, 3\}$，则你可以在一次操作中移除的元素有：

• 第 $1$ 个元素；
• 第 $1$ 个和第 $3$ 个元素；
• 第 $1$、第 $3$、第 $4$ 个元素；
• 第 $3$ 个和第 $4$ 个元素；
• 第 $2$、第 $4$、第 $5$ 个元素；
• 以及其它若干种组合。

但是，你不能选择第 $2$、第 $3$、第 $4$ 个元素，因为第 $2$ 个元素不等于第 $4$ 个元素，但第 $3$ 和第 $4$ 个元素相等。

对于每个 $x$ 从 $0$ 到 $n-1$，你需要计算将数组长度减少到恰好 $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$ 所需的最少操作次数。

在第一个示例中，答案可以如下得到：

• $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}$。

由 ChatGPT 5 翻译