edit I indeed was mistaken. The suggested answer is correct as far as I checked (n=10). It is easy enough to set up a system of equations for the expectations and compute. Here are the results to 6, the notation should be clear enough:
$$p_{12}=3,p_{111}=4 $$
$$p_{13}=11/2,p_{22}=7,p_{112}=8,p_{1111 }=9 $$
$$p_{14}={\frac {25}{3}},p_{23}={\frac {35}{3}} ,p_{1^23}={\frac {38}{3}},p_{12^2}=14,p_{1^32}=15,p_{1^5}=16 $$
` $p_{15}={\frac {137}{12}},p_{24}={\frac {101}{ 6}},p_{3^2}={\frac {37}{2}},p_{1^24}={\frac {107}{6}},p_{123} ={\frac {83}{4}}, p_{1^33}={\frac {87}{4}},p_{2^3}=22 ,p_{1^22^2}=23,p_{1^52}=24,p_{1^6}=25 $
AT least up to n=10, If two ones are replaced by a 2, the expected number of moves goes down by 1.