F. 数组缩减

时间限制： 每测试 $3$ 秒
内存限制： 每测试 $256$ 兆字节

给你一个包含 $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 \leq t \leq 10^4)$ — 测试用例的数量。

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

• 第一行包含一个整数 $n$ $(1 \leq n \leq 3 \cdot 10^5)$ — 数组的大小；
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \leq a_i \leq 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$。