P9843 [ICPC 2021 Nanjing R] Paimon Sorting

派蒙刚刚发明了一种新的排序算法，看起来很像“冒泡排序”，但有一些不同之处。它接受一个长度为 $n$ 的从 1 开始索引的序列 $A$ 并对其进行排序。其伪代码如下所示。 ```cpp // 排序算法 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)$ 时执行的交换次数。

有多个测试用例。输入的第一行包含一个整数 $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$。

对于每个测试用例，输出一行，包含 $n$ 个用空格分隔的整数 $s_1, s_2, \cdots, s_n$，其中 $s_i$ 是调用 $\text{SORT}(A_i)$ 时执行的交换次数。 请不要在每行的末尾输出多余的空格，否则你的解答可能会被判为错误！

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