Kata

This Kata is based on Kata "Simple Fun #148: Exchange Sort(myjinxin2015)", but this time the input sequence is not restricted to 3 different elements, only.

Task

Sorting is one of the most basic computational devices used in Computer Science.

Given a sequence (length ≤ 5000) of values (duplicates allowed), your task is to find the minimum number of exchange operations necessary to make the sequence sorted.

One operation is the switching of 2 key values in the sequence.

Example

For sequence = ["A", "A", "B", "B", "C"], the result should be 0.

It's already a sorted sequence.

For sequence = [9, -2, 1, 1, 9, -2], the result should be 1.

We can switching sequence[0] and sequence[5].

For sequence = [1, 2, 3, 0], the result should be 3.

We can:
 [1, 2, 3, 0] 
 switching sequence[0] and sequence[3]
 --> [0, 2, 3, 1]
 switching sequence[1] and sequence[3]
 --> [0, 1, 3, 2]
 switching sequence[2] and sequence[3]
 --> [0, 1, 2, 3]

For sequence = [8, 8, 3, 9, 9, 9, 8, 9, 3], the result should be 4.

We can:
 [8, 8, 3, 9, 9, 9, 8, 9, 3] 
 switching sequence[0] and sequence[3]
 --> [9, 8, 3, 8, 9, 9, 8, 9, 3]
 switching sequence[0] and sequence[8]
 --> [3, 8, 3, 8, 9, 9, 8, 9, 9]
 switching sequence[1] and sequence[2]
 --> [3, 3, 8, 8, 9, 9, 8, 9, 9]
 switching sequence[5] and sequence[7]
 --> [3, 3, 8, 8, 8, 9, 9, 9, 9] 
So 4 is the minimum number of operations for the sequence to become sorted.

Input/Output

[input] array sequence

The Sequence.

[output] an integer

the minimum number of operations needed to completly sort the input sequence.