Thornhill Computer Club 2023 - September Contest - Problem 6

JoePeewee loves burgers.

What he loves the most about burgers is the order in which he consumes this greasy fast food.

Specifically, he sorts these burgers by height from least to greatest.

After staring at the line of ~N~ burgers for 10 hours, he wonders what would be the least amount of swaps he could do to sort the line of burgers.

A swap is defined as taking two burgers and swapping their locations in the line.

JoePeewee has hired you, a professional programmer to help him with this conundrum.

Input Specification

The first line of the input contain integer ~N~, where ~1 \le N \le 10^4~

The next ~N~ lines contain integer ~h~, where ~1 \le h \le 10^4~, the height of each burger in order.

Output Specification

Output the least number of swaps required to sort the burgers, or 0 if the burgers are already in order.

Sample Input 1

5
3 2 1 4 1

Sample Output 1

3

Explanation for Sample Output 1

Swapping index 1 and 2 leaves us with 3 1 2 4 1.

Then swapping index 0 and index 4 leaves 1 1 2 4 3.

Finally, by swapping index 3 and 4, we are left with 1 1 2 3 4.

Ouput 3 since we swapped 3 times.

Sample Input 2

5
1 1 1 3 3

Sample Output 2

0