What is the min # of moves to sort an array from 1 to n?

Problem: You are required to sort an array with numbers from 1 to n. You can do a "move", which means choosing one element and moving it to
any place you want (insert to any place, not swap). Prove the minimum number of "moves" to sort the array is n - k, where k = the length of the longest increasing subsequence.

Ex: array is [1, 2, 5, 3, 4, 7, 6]

Longest increasing subsequence is [1, 2, 3, 4, 6], which is of length 5. Hence, the answer is 7 - 5 = 2 moves. You move numbers 5 and 7 to the correct spots.

I'd like a proof / intuition on why this has to be the minimum # of moves.

There is an invariant that each move can only increase the number in your longest increasing subsequence by at most 1.

If your initial array has $k$ values in its longest increasing subsequence, you need $n-k$ moves at least to get it sorted.
This shows $n-k$ moves is necessary.

StackExchange Computer Science Q#29579, answer score: 8