Sorting an array

There's an array of values from 1 to n. It isn't sorted. We have to sort it, but there are only to ways to move: third element to beginning or last element to beginning. How to do that ?

Simplify the operations a bit; last → first is just rotation; use that to seek, and you have just one operation: move any element two positions forward.
For even sized arrays this lets you move any element anywhere, for odd-sized arrays you have to first rotate the element to the correct modulo-2 position, and you'll end up with a sorted or almost sorted array.

A more interesting question is how to prove the unsolvable cases can't be solved. I found an invariant using the Lehmer code — probably, but it's kind of a pain to make a formal proof.