Description

In this PRoblem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence

9 1 0 5 4 ,

Ultra-QuickSort produces the output

0 1 4 5 9 .

Your task is to determine how many swap Operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 – the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

Sample Output

題意

求把一個序列排序所需要的最小相鄰交換次數。

思路

題目可以轉化為求數組所有數字的逆序數之和，因為n比較大的關系，所以舍棄 O(n2)$O(n^2)$ 的算法，改用歸并排序。

一般這樣的題目都可以用歸并排序來解決，或者樹狀數組也可以。

假設當前歸并排序的兩個序列為

1 3 4 9

2 5 7 8

分別取數3、2，3>2，說明3后面所有的數都比2大(m-p)，因為序列1一定在序列2前面，那這一個解釋便是逆序數咯！

另外，當序列2全部排序完之后序列1還剩9，此時可以得到，9以及后面的所有的數都比序列2大(y-m)。

AC 代碼