OMC015(E)

点数: 500

Writer: simasima

　正の整数からなる有限列 $X$ があります. $X$ に対して, 以下の手順からなる操作を繰り返し行います.

• まず, 隣り合う $2$ 数を選択する. ただし, 両端に位置する数を含んではならない.
• 隣り合う $2$ 数がともに $2$ 以上のとき, 選択した $2$ 数をそれぞれ $1$ 減らし, 間に $1$ を $2$ つ挿入する.
• 隣り合う $2$ 数がともに $1$ のとき, これらの両隣に位置する $2$ 数をそれぞれ $1$ 増やし, 選択した $2$ 数を削除する.
• 隣り合う $2$ 数の一方のみが $1$ のとき, $1$ でない方を $1$ 減らし, $1$ である方に隣り合っておりかつ選択されていない数を $1$ 増やす.

　例えば, 以下のように操作が進みます： $$\lbrace 2,(3,7),8,1,4\rbrace\rightarrow \lbrace 2,2,(1,1),6,8,1,4\rbrace\rightarrow \lbrace 2,3,7,(8,1),4\rbrace\rightarrow \lbrace 2,3,7,7,1,5\rbrace$$ 　$X$ の長さが $3$ 以下になった時点で操作を終了します. 操作は必ず有限回で終了できることが証明できます. $$X=\lbrace 3,4,4,2,1,4,4,1,1,2,2,1,3,1,1,3,4,2,3,2,4,1\rbrace$$ $X$ を上のように定めたとき, 操作を最小で $M$ 回繰り返せば終了します. $M$ を解答してください.