D. Minimum Inversions
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence $$$a$$$ of length $$$n$$$. There is a sequence $$$b$$$ which is initially empty. You need to perform $$$n$$$ operations.

In the $$$i$$$-th operation, you can choose one of the following two types of operations:

  1. insert $$$a_i$$$ into the beginning of $$$b$$$;
  2. insert $$$a_i$$$ into the end of $$$b$$$.

Solve the following problem for each $$$j$$$, where $$$0 \le j \le n$$$: find the minimum possible number of inversions$$$^\dagger$$$ in $$$b$$$ if exactly $$$j$$$ operations of the first type are performed.

$$$^\dagger$$$ An inversion in a sequence is a pair of elements where the earlier element is greater than the later element. In other words, for a sequence $$$b$$$, a pair $$$(b_i, b_j)$$$ is an inversion only if $$$i \lt j$$$ and $$$b_i \gt b_j$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of test cases. For each test case:

  • The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$).
  • The second line contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output $$$n+1$$$ integers. The $$$j$$$-th integer should be the minimum possible number of inversions when exactly $$$j$$$ operations of the first type are performed, for $$$j=0,\ldots,n$$$.

Example
Input
3
2
2 1
5
3 2 4 1 2
6
3 2 6 1 5 4
Output
1 0 0
6 3 2 1 1 3
7 4 3 3 4 6 8
Note

Consider the first test case.

  • If $$$j = 0$$$, the only way is to do two operations of the second type. After that, $$$b=[2,1]$$$ and the number of inversions is $$$1$$$.
  • If $$$j = 1$$$, the optimal way is to perform an operation of the second type and then perform an operation of the first type. After that, $$$b=[1,2]$$$ and the number of inversions is $$$0$$$.
  • If $$$j = 2$$$, the only way is to do two operations of the first type. After that, $$$b=[1,2]$$$ and the number of inversions is $$$0$$$.