题目描述

给定一个由 $n$ 个互不相同的整数组成的序列，每次可以交换相邻的两个数字。请问最少需要交换多少次，才能使序列变成升序序列？

输入格式

输入包含多组测试数据。

每组数据的第一行是一个正整数 $n$，表示序列的长度。当 $n=0$ 时表示输入结束。

接下来 $n$ 行，每行一个整数 $a_i$，表示序列中第 $i$ 个元素。

输出格式

对于每组测试数据，输出一行一个整数，表示将序列变为升序所需的最少相邻交换次数。

样例

5
9
1
0
5
4
0

6

提示

序列为 $[9, 1, 0, 5, 4]$。最少相邻交换次数为 $6$（即序列的逆序对个数）。

• 例如：$(9,1)$、$(9,0)$、$(9,5)$、$(9,4)$、$(1,0)$、$(5,4)$ 共 $6$ 对逆序对。

数据范围

• $1 \le n < 500000$（$n=0$ 时表示输入结束）
• $0 \le a_i \le 999999999$，所有 $a_i$ 互不相同

来源

CodesOnline