CF2141F Array Reduction

You are given an array $$$a$$$ containing $$$n$$$ integers. In one operation, you can choose some elements from this array and remove them. However, the elements you choose must meet one of the following conditions: - either all chosen elements are equal; - or there are no two equal chosen elements. Note that if you choose only $$$1$$$ element to remove, it automatically meets these conditions. For example, if $$$a = \\{1, 2, 1, 1, 3\\}$$$, some of the possible elements you can remove in one operation are: - the $$$1$$$-st element; - the $$$1$$$-st and the $$$3$$$-rd element; - the $$$1$$$-st, the $$$3$$$-rd and the $$$4$$$-th element; - the $$$3$$$-rd and the $$$4$$$-th element; - the $$$2$$$-nd, the $$$4$$$-th and the $$$5$$$-th element; - and many others. However, you cannot choose the $$$2$$$-nd, the $$$3$$$-rd and the $$$4$$$-th element because the $$$2$$$-nd element is not equal to the $$$4$$$-th, but the $$$3$$$-rd element is equal to the $$$4$$$-th. For each $$$x$$$ from $$$0$$$ to $$$n - 1$$$, you have to calculate the minimum number of operations required to decrease the size of the array to exactly $$$x$$$.

The first line contains one integer $$$t$$$ ($$$1 \\le t \\le 10^4$$$) — the number of test cases. Each test case consists of two lines: - the first line contains one integer $$$n$$$ ($$$1 \\le n \\le 3 \\cdot 10^5$$$) — the size of the array; - the second line contains $$$n$$$ integers $$$a\_1, a\_2, \\dots, a\_n$$$ ($$$1 \\le a\_i \\le n$$$) — the array itself. Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \\cdot 10^5$$$.

For each test case, print $$$n$$$ integers $$$c\_0, c\_1, \\dots, c\_{n-1}$$$, where $$$c\_i$$$ is the minimum number of operations required to reduce the size of the array to exactly $$$i$$$.

In the first example, the answer can be obtained as follows: - $$$c\_{0} = 3$$$: remove $$$a\_{8}, a\_{9}, a\_{10}, a\_{11}$$$; then remove $$$a\_{1}, a\_{2}, a\_{3}, a\_{4}$$$; then remove $$$a\_{5}, a\_{6}, a\_{7}$$$; - $$$c\_{1} = 3$$$: remove $$$a\_{8}, a\_{9}, a\_{10}, a\_{11}$$$; then remove $$$a\_{1}, a\_{2}, a\_{3}, a\_{4}$$$; then remove $$$a\_{5}, a\_{6}$$$; - $$$c\_{2} = 2$$$: remove $$$a\_{7}, a\_{8}, a\_{9}, a\_{10}, a\_{11}$$$; then remove $$$a\_{1}, a\_{2}, a\_{3}, a\_{4}$$$; - $$$c\_{3} = 2$$$: remove $$$a\_{7}, a\_{8}, a\_{9}, a\_{10}, a\_{11}$$$; then remove $$$a\_{1}, a\_{2}, a\_{3}$$$; - $$$c\_{4} = 2$$$: remove $$$a\_{7}, a\_{8}, a\_{9}, a\_{10}, a\_{11}$$$; then remove $$$a\_{1}, a\_{2}$$$; - $$$c\_{5} = 1$$$: remove $$$a\_{1}, a\_{7}, a\_{8}, a\_{9}, a\_{10}, a\_{11}$$$; - $$$c\_{6} = 1$$$: remove $$$a\_{7}, a\_{8}, a\_{9}, a\_{10}, a\_{11}$$$; - $$$c\_{7} = 1$$$: remove $$$a\_{1}, a\_{2}, a\_{3}, a\_{4}$$$; - $$$c\_{8} = 1$$$: remove $$$a\_{1}, a\_{2}, a\_{3}$$$; - $$$c\_{9} = 1$$$: remove $$$a\_{1}, a\_{2}$$$; - $$$c\_{10} = 1$$$: remove $$$a\_{7}$$$;