Ultra-QuickSort#1303
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For example, for the input sequence
9 1 0 5 4
Ultra-QuickSort produces the output
0 1 4 5 9
Your task is to determine the minimum number of adjacent swaps necessary to sort a given input sequence in ascending order.
The input consists of several test cases. The first line of each test case contains the length of the input sequence (n \leq 500\,000). Each of the following lines contains a single integer a_i (0 \leq a_i \leq 999\,999\,999), the -th sequence element. The last test case contains n = 0 and should not be processed.
For every input sequence, print a single line containing an integer — the minimum number of adjacent swaps necessary to sort the sequence.
Example 1