与えられた n 個の整数を昇順に並べ替えてください。操作として、配列の中から1つの要素を選び、その要素を配列の先頭に移動することができます。配列を完全にソートするには、最小で何回その操作を行えばよいでしょうか?
入力
入力の最初の行には、整数 n (1 ≤ n ≤ ) が1つ与えられます。
次の行には、配列の要素として n 個の整数 (1 ≤ ≤ ) がスペース区切りで与えられます。
出力
配列をソートするのに必要な操作の最小回数を出力してください。
例
入力 | 出力 |
6
11 13 15 12 14 16 | 4 |
10
1 3 2 4 2 4 4 5 9 10 | 3 |
8
3 5 1 5 5 6 7 10 | 1 |
1番目の例の説明
- 14 を先頭に移動する
- 13 を先頭に移動する
- 12 を先頭に移動する
- 11 を先頭に移動する
2番目の例の説明
- 2 を先頭に移動する
- もう一つの 2 を先頭に移動する
- 1 を先頭に移動する