から までの番号がついた 人の学生がいます。学生は横一列に並んでおり、左から 番目には番号 の学生がいます。今から学生たちは先生の指示に従って左から番号が小さい順に整列します。
先生は「学生 人を指名して、位置を入れ替える」という指示を出して、生徒を移動させます。これ以外の方法で学生が移動することはできません。移動にはコストがかかり、左から 番目の学生と左から 番目の生徒が位置を入れ替わる場合 のコストがかかります。
先生は学生が正しく整列するまで指示を出します。 移動のコストの合計が最小になるよう指示を出したとき、その合計はいくらですか。
入力は以下の形式で標準入力から与えられます。
移動のコストの合計を出力してください。
2 2 1
1
先生は、左から 番目の学生と左から 番目の学生を入れ替える指示を出します。 このときコストは かかります。並び順は となり、整列が完了します。
このときのコストが最小です。
10 6 4 1 2 10 8 9 3 7 5
16