Ultra-QuickSort
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
Сonsists of several test cases. The first line of each test case contains the length of the input sequence n (n ≤ 500,000). Each of the following n lines contains a single integer a[i] (0 ≤ a[i] ≤ 999999999), the i-th input sequence element. The last test case contains n = 0 and is not processed.
Output
For every input sequence print a single line containing an integer number op - the minimum number of swap operations necessary to sort the given sequence.