F. Array Reduction
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Input

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$$$.

Output

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$$$.

Example
Input
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
Output
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
Note

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}$$$;