Description

派蒙刚刚发明了一种新的排序算法，看起来很像“冒泡排序”，但有一些不同之处。它接受一个长度为 $n$ 的从 1 开始索引的序列 $A$ 并对其进行排序。其伪代码如下所示。

// 排序算法
SORT(A)
  for i from 1 to n // n 是 A 中元素的数量
    for j from 1 to n
      if a[i] < a[j] // a[i] 是 A 中的第 i 个元素
        Swap a[i] and a[j]

如果你不相信这段算法可以对一个序列进行排序，你的任务就是证明它。无论如何，问题如下：

给定一个整数序列 $A = a_1, a_2, \cdots, a_n$，对于其每个长度为 $k$ 的前缀 $A_k$（即，对于每个 $1 \le k \le n$，考虑子序列 $A_k = a_1, a_2, \cdots, a_k$），计算调用 $\text{SORT}(A_k)$ 时执行的交换次数。

Input Format

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$)，表示给定的序列。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

Output Format

对于每个测试用例，输出一行，包含 $n$ 个用空格分隔的整数 $s_1, s_2, \cdots, s_n$，其中 $s_i$ 是调用 $\text{SORT}(A_i)$ 时执行的交换次数。

请不要在每行的末尾输出多余的空格，否则你的解答可能会被判为错误！

3
5
2 3 2 1 5
3
1 2 3
1
1

0 2 3 5 7
0 2 4
0

Hint

题面翻译由 ChatGPT-4o 提供。