言われてみればなるほど。
本番中は1を追加する場所を全部試すとMを追加する場所が高速に求まったりするのかな？という方向で考えてたけどちょっと外してた感。
まず、同じ値が並べばコストは0。 差が1ならコスト1なので、隣り合う値がaとbのときコストをb-aとすると、この間にaからbの値を順番に入れれば、コストはb-aのまま変わらない。
言い換えると、aとbの間に c または
を追加してもコストは変わらない。
よって入力Aの最小値と最大値を求めると、この最小値から最大値の間の値はコストを変化させずに、Aのどこかの間に入れることができる。
さらに、1から最小値、最大値からMの値は昇順または降順に任意の間にいれるのが最善となる。
そして上記の通りコストは変わらないので実質1とMをどこにいれるかという問題になる。
任意の場所(iとi+1の間）に1を追加することを考える。
このときにコストの変化は となる。
よって予めAのコストを求めてから、1を追加する場所を全部ためして最小値を取れば、1を追加する場所はで求めることができる。
同様にMを追加する場所を求めることができる。
問題は1とMを同じ場所に追加する時だが、上の方法で1とMを同じ場所に追加したときのコストの計算結果は、正しくコストを求めた時よりも絶対に大きくなるので、(答えとして最小値をとるので)そのまま処理をしてよい。
その上で、1とMを同じ場所に追加する場合は、任意の場所に「1 M」と追加するときと「M 1」と追加するときの両方を試して最小値をとれば求める答えになる。
ちょっとした注意点として、全部まとめて処理して最小値をとることは（たぶん）できないので処理をわけて丁寧にやる必要がある。
