给定一个数组 $$$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$$$ 所需的最小操作数。
示例
输入复制
5115 5 5 5 2 2 2 8 6 1 763 3 3 3 3 352 1 3 5 481 1 1 2 3 4 5 611
输出复制
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}$$$;