This is the type of the problem that looks at its inverse - i.e., instead of finding out what moves, find what did not move and its extreme values.

Focus on the unknown, what properties can you infer from the unknown?

  1. The unmoved parts, after moves, will be collapsed together, i.e., they must be consecutive numbers

  2. Therefore, # of unmoved <= # of items where consecutive numbers have increasing indices, i.e., max(# of unmoved) <= max(# of consecutive numbers with increasing indices) 

  3. Can the upper bound always be reached? i.e., does that longest sequence give the answer we need?

  4. Then we need to prove max(# of unmoved) >= max(# of consecutive numbers with increasing indices) 

  5. To prove 4), we can argue that we can always construct a solution around that subsequence, easily prove by induction

  6. Therefore, by 2) and 4), we just need to find longest consecutive value sequences with increasing indicies => use the inverse index