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.
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).
For each test case, print one line containing
where M is the minimum number of flip operations required to perform sorting.
Output for Sample Input
|University of Debrecen; Faculty of Informatics; v. 05/24/2018|