No.365 ジェンガソート

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 295
作問者 : 🍡yurahuna🍡yurahuna / テスター : btkbtk
22 ProblemId : 1081 / 出題時の順位表

問題文

$N$ 個のブロックが横一列に並んでいます。ブロックの長さはそれぞれ $1, 2, ..., N$ ですが、順番はバラバラです。
yurahuna君は、ブロックを左から見て長さの小さい順になるように並び替えることにしました。
ただしyurahuna君にできるのは「ブロックを1つ選び、そのブロックを一番左に移動する」という操作のみです。
(もし一番左のブロックを選んだ場合、操作後のブロックの並びは変わりませんが、これも1回の操作と数えることにします。)

さて、yurahuna君は最小何回の操作でブロックを並び替えることができるでしょうか?

入力

$N$
$a_1$ $a_2$ ... $a_N$

  • 1行目には、ブロックの個数 $N$ $(1 \leq N \leq 100000)$ が与えられる。
  • 2行目には、ブロックの長さ $a_i$ $(1 \leq i \leq N, 1 \leq a_i \leq N)$ がスペース区切りの整数で与えられる。
    $a_i$ は左から $i$ 番目のブロックの長さを表す。
    • ブロックの長さはすべて異なる。すなわち、すべての $i, j$ $(1 \leq i < j \leq N)$ について、$a_i \neq a_j$ である。

出力

yurahuna君がブロックを並び替えるのにかかる最小の操作回数を1行で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
5
3 1 4 2 5
出力
2

まず長さ2のブロックを選んで一番左に移動し、次に長さ1のブロックを選んで一番左に移動すると、左から見て長さの小さい順になります。これは操作回数が最小となる並び替え方です。
3 1 4 2 5

2 3 1 4 5

1 2 3 4 5

サンプル2
入力
4
4 3 2 1
出力
3

長さ3, 2, 1の順にブロックを選んで操作すると最小回数で並び替えられます。

サンプル3
入力
4
1 2 3 4
出力
0

既に左から見て長さの小さい順になっているので、yurahuna君は1回も操作を行わなくてよいです。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。