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 ai (0 ≤ ai ≤ 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.