2021-ビーバーソート

川には長さが異なる丸太がいくつかあります．ビ太郎の仕事は，丸太を長さ順に並び替えることでです．ビ太郎は川岸に沿って移動し、必ず2つの丸太の間で止まります．両隣の2本の丸太の長さを比較して、必要であれば入れ替えます。

ビ太郎は，最初にどのような並びで丸太が入ってきても，以下のようにして丸太を長さ順に並べ替えられることを知っています．

• 左端の丸太の右側の位置から始めます．
• 左端の丸太の右側から始めて，右端の丸太の右側に来るまで次を繰り返します:
  • 左側の丸太が右側の丸太よりも短い場合は，丸太1本分右に移動します．
  • 右側の丸太が左側の丸太よりも短い場合は，これらの丸太を入れ替えてます．入れ替えたあと，開始位置（左端の丸太の右側の位置）にいなければ，丸太1本分左に移動します．

ビ太郎が4本の丸太をどのように並べ替えるか見てみましょう．この例では，ビ太郎は9回動きます．（実際に動いた場合のみを数えています．左端の開始位置にいて，丸太を入れ替えたものの移動しなかった場合は数えません．）

ビ太郎が丸太を並び替えるのに動く回数は，丸太が最初にどのように入ってきたかによって決まります．最悪の場合，6本の丸太を並び替えるのにビ太郎は25回の動く必要があります．（左端の開始位置にいて，入れ替えたものの移動しなかった回数は5回です．）

チャレンジ:
ビ太郎は60個の丸太を並び替えないとなりません．ビ太郎が動く回数は，次のどの範囲に収まっているでしょう？