24179번 - 回転 다국어

1 以上 N 以下の相異なる整数からなる，長さ N の整数列 P = (p₁, p₂, ..., p_N) がある．あなたは，この整数列の連続する部分列を選び，回転という操作を行うことができる．より厳密には，あなたは，次の二種類の操作を，任意の順序で任意の回数行うことができる．

• 1 ≤ b < e ≤ N を満たす二つの整数 b ,e を選ぶ．連続部分列 p_b, ..., p_e の先頭の要素を，その連続部分列の末尾へ移動させる．すなわち，p_b, p_b+1, p_b+2, ..., p_e-2, p_e-1, p_e を，p_b+1, p_b+2, p_b+3, ..., p_e-1, p_e, p_b に，それぞれ変更する．
• 1 ≤ b < e ≤ N を満たす二つの整数 b ,e を選ぶ．連続部分列 p_b, ..., p_e の末尾の要素を，その連続部分列の先頭へ移動させる．すなわち，p_b, p_b+1, p_b+2, ..., p_e-2, p_e-1, p_e を，p_e, p_b, p_b+1, ..., p_e-3, p_e-2, p_e-1 に，それぞれ変更する．

いずれの操作についても，一回あたり，選んだ連続部分列の長さすなわち e-b+1 だけのコストがかかる．

あなたは，これらの操作を用いて，整数列 P の要素を昇順に並べ替えたい．すなわち，任意の 1 ≤ i ≤ N に対し p_i = i を満たすようにしたい．このために必要なコストの総和の最小値を求めよ．

入力は 50 個以下のデータセットからなる． 各データセットは次の形式で表される．

N
p1 p2 … pN

1 行目には，整数列の長さ N (2 ≤ N ≤ 10⁵) が与えられる．2 行目には，整数列 P の各要素 p_i (1 ≤ p_i ≤ N) が，空白区切りで与えられる．i ≠ j ならば p_i ≠ p_j であることが保証される．

入力の終わりは 1 つのゼロからなる行で表される．

各データセットに対し，あなたが整数列 P を昇順に並べ替えるために必要なコストの総和の最小値を，1 行に出力せよ．