Finished with a full-state search of 12; worst case is indeed 130. Found a game for n=14 that takes 172 moves: 6 11 8 2 7 10 9 12 4 1 14 3.