proof by ac:)

The principle behind this is pretty similar to insertion sort's: first consider a sorted subsequence of the array. Then, for every element not in this subsequence, relocate them into their correct position in the array. Therefore, the minimum number of relocations one has to do is equal to the number of out-of-place elements.

For instance, take the array 3, 1, 5, 2, 4 for example, take 3, 5 to be the sorted subsequence (this isn't the optimal solution — for demonstrational purposes only!)

3 1 5 2 4 → 1 3 5 2 4 → 1 2 3 5 4 → 1 2 3 4 5

This would take 3 steps: N — length of sorted subsequence. Bolded elements denote sorted elements. Note that the initial positions of the unsorted elements don't matter — they will be relocated anyways.

Naturally, since we want to minimise the number of relocations, we would want to take the longest nondecreasing subsequence as the initial sorted subsequence. Therefore, the answer to this problem is indeed N minus the length of the longest non-dec subsequence.