070803 - How many times do you need to exchange?

題目敘述 Problems Description:

在這個問題中，你必須分析特定的排序演算法。該演算法通過交換兩個相鄰的序列元素，來處理由n個不同整數所組成的序列，直到該序列以升序排序。

以輸入序列 9 1 0 5 4來說，經過排序後會得到輸出0 1 4 5 9。

你需要做的是計算排序過程中，需要經過幾次交換才能完成排序。

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 Description:

輸入包含數個測資，每一組測資的第一行為一個整數n < 500,000，n 為序列的長度，接下來的n 行輸入，每一行的輸入為一個整數a[i]，i 為第i個序列元素，若輸入一個序列的長度為n=0，則終止程式。

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 — the length of the input sequence. Each of the the following n lines contains a single integer, the i-th input sequence element. Input is terminated by a sequence of length n = 0.

This sequence must not be processed.

輸出說明 Output Description:

每一組輸入的序列，需要輸出一個整數op，op為排序完成最少需要經過的交換次數。

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

輸入範例 Input Example:

5

9

1

0

5

4

3

1

2

3

0

輸出範例 Output Example:

6

0