Flip Sort

Sorting in computer science is an important part. Almost every problem can be solved efficiently if sorted data are found. There are some excellent sorting algorithms, which have already acheived the lower bound complexity of n · log n. In this problem, we will discuss about a new sorting approach. In this approach, only one operation (flip) is available, with which two adjacent terms can be exchanged. If you think for a while, you will see that it is always possible to sort a sequence of numbers in this way.

A sequence of integers will be given. Now, using the above approach, we want to sort the numbers in ascending order. You have to find the minimum number of flips required. For example, to sort the sequence 1, 2, 3, we need no flip operation, whereas to sort 2, 3, 1, we need at least 2 flip operations.

Input Specification

The input contains several test cases. Each test case starts with a positive integer N (N ≤ 1000). In the next few lines, there will be N integers, constituting the sequence of numbers to be sorted. The input will be terminated by end-of-file (EOF).

Output Specification

For each test case, print one line containing

“Minimum exchange operations : M”,

where M is the minimum number of flip operations required to perform sorting.

Sample Input

1. 3
2. 1 2 3
3. 3
4. 2 3 1

download as text file

Output for Sample Input

1. Minimum exchange operations : 0
2. Minimum exchange operations : 2

download as text file