Out of Place

Farmer John wants to take a photo of his entire herd of cows. To make the photo look more appealing, he arranged the cows in order of increasing height. However, after the cows lined up, the mischievous Bessie stepped out of line and reinserted herself at a different position, disturbing the order.

Your task is to determine the minimum number of swaps required to restore the order by swapping pairs of cows.

Let \(N\) denote the total number of cows and let the array \(A\) represent their current heights. Let \(A_{sorted}\) be the sorted version of \(A\) (in non-decreasing order). Define the number of positions where \(A[i] \neq A_{sorted}[i]\) as \(\text{diff}\). Then, the answer will be:

[ \text{ans} = \max(0, \text{diff} - 1)]

If the cows are already in order, no swaps are needed.

inputFormat

The first line contains a single integer \(N\) (the number of cows). The following \(N\) lines each contain a single integer representing the height of a cow in the current order.

outputFormat

Output a single integer representing the minimum number of swaps required to restore the order.

sample

6
2
4
7
7
9
3

3