Description

You are now given a sequence consisting of n distinct integers. The task is to swap adjacent elements any number of times to make the sequence ascending. What is the minimum number of swaps required?

Input Format

The input contains multiple test cases. For each test case, the first line is a positive integer n (n < 500000), representing the length of the sequence. When n = 0, the input ends.

The following n lines each contain an integer a[i] (0 ≤ a[i] ≤ 999999999), representing the i-th element of the sequence.

Output Format

For each test case, output the minimum number of swaps required to sort the given sequence in ascending order.

```input1 5 9 1 0 5 4 3 1 2 3 0 ``` ```output1 6 0 ``` ## 译文

CodesOnline