**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.