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 翻译