31178번 - Paimon Sorting 다국어

문제

Paimon just invents a new sorting algorithm which looks much like bubble sort, with a few differences. It accepts a 1ドル$-indexed sequence $A$ of length $n$ and sorts it. Its pseudo-code is shown below.

Functions 1 The Sorting Algorithm

1. function Sort($A$)
2. for $i$ ← 1ドル$ to $n$ do // $n$ is the number of elements in $A$
3. for $j$ ← 1ドル$ to $n$ do
4. if $a_i < a_j$ then // $a_i$ is the $i$-th element in $A$
5. Swap $a_i$ and $a_j$

If you don't believe this piece of algorithm can sort a sequence it will also be your task to prove it. Anyway here comes the question:

Given an integer sequence $A = a_1, a_2, \cdots, a_n$ of length $n,ドル for each of its prefix $A_k$ of length $k$ (that is, for each 1ドル \le k \le n,ドル consider the subsequence $A_k = a_1, a_2, \cdots, a_k$), count the number of swaps performed if we call $\text{SORT}(A_k)$.

입력

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ (1ドル \le n \le 10^5$) indicating the length of the sequence.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ (1ドル \le a_i \le n$) indicating the given sequence.

It's guaranteed that the sum of $n$ of all test cases will not exceed 10ドル^6$.

출력

For each test case output one line containing $n$ integers $s_1, s_2, \cdots, s_n$ separated by a space, where $s_i$ is the number of swaps performed if we call $\text{SORT}(A_i)$.

제한

힌트