Out of Place

Time limit2sMemory limit512 MB

Summary

Given a row that came from a sorted row with one cow moved, find the minimum number of arbitrary swaps to sort it.

Level: Medium4 of 10
Topics: Sorting, Greedy, Array
Solved: No attempts yet

Problem

Farmer John wants a single photograph of his whole herd.

For the picture to look right, the cows have to stand in one row from shortest to tallest. Right after Farmer John lines them up that way, Bessie, who always causes trouble, steps out of the row and squeezes back in somewhere else.

Farmer John repairs the row by swapping pairs of cows. Find the smallest number of swaps that puts the herd back in order from shortest to tallest. The two cows in a swap do not have to stand next to each other.

Input

The first line contains the number of cows $N$ ( $2 \le N \le 100$ ). Each of the next $N$ lines contains the height of one cow, in the order the cows stand after Bessie moves. Every height is an integer between $1$ and $1\,000\,000$ , and several cows may have the same height. The row you are given is what you get when one cow leaves a row sorted from shortest to tallest and steps back in at another position.

Output

Print the smallest number of swaps needed to sort the row from shortest to tallest.

Hint

Suppose six cows stand with heights $2, 4, 7, 7, 9, 3$ . Bessie is the cow of height $3$ , and Farmer John sorts the row with three swaps.

2 4 7 7 9 3   (original lineup)
2 4 7 7 3 9   (swap the last two cows)
2 4 3 7 7 9   (swap the first 7 and the 3)
2 3 4 7 7 9   (swap the 4 and the 3)

Examples3

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