There is always a loop: a--b--c...--a (means a need to take b's position, etc). Using this fact you can easily get a linear algorithm.