题目描述

本题需要分析一种特定的排序算法。该算法通过不断交换相邻元素的方式，将一个包含$n$个不同整数的序列排序为升序排列。例如对于输入序列：

$9\ 1\ 0\ 5\ 4$

经过一系列相邻交换后，最终得到有序序列：

$0\ 1\ 4\ 5\ 9$

任务：计算该排序算法需要对给定输入序列执行的最少交换次数。

输入格式

• 包含多个测试用例
• 每个测试用例以整数$n$开头（$n < 500,000$），表示序列长度
• 随后$n$行每行一个整数$a[i]$（$0 \leq a[i] \leq 999,999,999$）
• 输入以$n=0$终止，该情况不需处理

输出格式

• 对每个测试用例，输出一个整数$op$，表示排序所需的最少交换次数

样例输入

5
9
1
0
5
4
3
1
2
3
0

样例输出

6
0

Waterloo 地区赛 2005.02.05