Obviously, the aliens can cheat.

Another solution is that the population is very small, or gets very small during the mating dance (aliens die during the dance and thus get removed from the line). It also makes sense to assume that the aliens are hermaphrodites.

The line also does not need to be straight, which can reduce the travel time from one position to another.