超快速排序交换次数问题

题目描述

在这个问题中，您必须分析特定的排序算法——超快速排序。

该算法通过交换两个相邻的序列元素来处理 $n$ 个不同整数的序列，直到序列按升序排序。

对于输入序列 9 1 0 5 4，超快速排序生成输出 0 1 4 5 9。

您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

输入格式

输入包括一些测试用例。

每个测试用例的第一行输入整数 $n$，代表该用例中输入序列的长度。

接下来 $n$ 行每行输入一个整数 $a_i$，代表用例中输入序列的具体数据，第 $i$ 行的数据代表序列中第 $i$ 个数。

当输入用例中包含的输入序列长度为 $0$ 时，输入终止，该序列无需处理。

输出格式

对于每个需要处理的输入序列，输出一个整数 $op$，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。

输入输出样例 #1

输入 #1

5
9
1
0
5
4
3
1
2
3
0

输出 #1

6
0

输入输出样例 #2

输入 #2

6
5
4
3
2
1
0
0

输出 #2

15

限制条件

• $0 \le n < 500000$
• 一个测试点中，所有 $n$ 的和不超过 $500000$
• $0 \le a_i \le 999999999$
• 序列中的元素互不相同

样例解释 #1

第一个测试用例

输入序列：$[9, 1, 0, 5, 4]$

通过交换相邻元素进行排序，最小交换次数为 $6$：

1. 交换 $9$ 和 $1$：$[1, 9, 0, 5, 4]$
2. 交换 $9$ 和 $0$：$[1, 0, 9, 5, 4]$
3. 交换 $1$ 和 $0$：$[0, 1, 9, 5, 4]$
4. 交换 $9$ 和 $5$：$[0, 1, 5, 9, 4]$
5. 交换 $9$ 和 $4$：$[0, 1, 5, 4, 9]$
6. 交换 $5$ 和 $4$：$[0, 1, 4, 5, 9]$

第二个测试用例

输入序列：$[1, 2, 3]$

序列已经有序，无需任何交换，交换次数为 $0$。

算法说明

这个问题实际上是求序列的逆序对数量。每次交换相邻元素可以消除一个逆序对，而排序完成需要消除所有逆序对，因此最小交换次数等于序列中的逆序对总数。