Change the assumptions of the proof.

The paper mentioned is "S. Skiena. Encroaching lists as a measure of presortedness. BIT, 28:775-784, 1988."