Description

You are now given a sequence consisting of n distinct integers. The task is to swap any two adjacent numbers 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 make the given sequence ascending.

```input1 5 9 1 0 5 4 3 1 2 3 0 ``` ```output1 6 0 ``` ## 代码在线