What is the min # of moves to sort an array from 1 to n?
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.