Observe that the rightmost 1 can be either in an even or odd position, so it might not be moved by the first odd–even pass. But after the first odd–even pass, the rightmost 1 will be in an even position. It follows that it will be moved to the right by all remaining passes. Since the rightmost one starts in position greater than or equal to formula_4, it must be moved at most formula_6 steps. It follows that it takes at most formula_7 passes to move the rightmost 1 to its correct position.