IIUC that's covered in the paper, as bozo-sort (or bozo-sort+ if the two random numbers are different).

I think it may helpful to decompose the permutation into circles, and create an equation system of time left from different states.