Ultra-QuickSort

Interview

Time limit1sMemory limit256 MB

Summary

Given a sequence of distinct integers, count the minimum number of adjacent swaps needed to sort it, which is the number of inversions.

Level: Medium6 of 10
Topics: Divide and conquer, Sorting, Binary search, Array
Solved: No attempts yet

Problem

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of $n$ distinct integers by repeatedly swapping two adjacent elements until the sequence is sorted in ascending order. For example, the sequence 9, 1, 0, 5, 4 becomes 0, 1, 4, 5, 9.

Your task is to determine the minimum number of swap operations Ultra-QuickSort needs in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line containing a single integer $n$ ( $n < 500{,}000$ ) — the length of the input sequence. Each of the following $n$ lines contains a single integer $a_i$ ( $0 \le a_i \le 999{,}999{,}999$ ), the $i$ -th element of the sequence. The integers within one test case are all distinct. The input is terminated by a sequence of length $n = 0$ , which must not be processed.

Output

For every input sequence, print a single line containing an integer $op$ , the minimum number of swap operations needed to sort that sequence.

Examples2

Example 1
Input
```
5
9
1
0
5
4
3
1
2
3
0
```
Expected output
```
6
0
```
Example 2
Input
```
1
42
0
```
Expected output
```
0
```