E. Cyclic Inversion
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a = [a_1, a_2, \dots, a_n]$$$ of length $$$n$$$.

An inversion is a pair of indices $$$(i, j)$$$ such that $$$1 \le i \lt j \le n$$$ and $$$a_i \gt a_j$$$. The inversion count of an array is the total number of inversions.

A cyclic shift of the first $$$k$$$ elements to the end of the array transforms $$$[a_1, a_2, \dots, a_k, a_{k+1}, \dots, a_n]$$$ into $$$[a_{k+1}, \dots, a_n, a_1, a_2, \dots, a_k]$$$.

For each $$$k = 1, ~2, ~\ldots, ~n - 1$$$, solve the following problem and print the answer.

  • Find the minimum inversion count achievable in the array $$$a$$$ after performing any number(possibly zero) of cyclic shifts of the first $$$k$$$ elements to the end. For example, if $$$a = [4, 3, 5, 3, 3]$$$ and $$$k = 2$$$, we can generate these arrays $$$[4, 3, 5, 3, 3] \longrightarrow [5, 3, 3, 4, 3] \longrightarrow [3, 4, 3, 5, 3] \longrightarrow [3, 5, 3, 3, 4] \longrightarrow \ldots$$$. And the minimum inversion count among these arrays is $$$1$$$.
Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.

For each test case, the first line contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$). The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print $$$n - 1$$$ space-separated integers in a new line, where the $$$k$$$-th integer is the answer for $$$k$$$.

Example
Input
2
4
2 3 3 1
5
4 3 5 3 3
Output
0 2 0
1 1 1 1