D - トランプ挿入ソート 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

数字が書かれたカードが N 枚あります。このカードの束（山札）に対して以下の操作が可能です。

  • 山札からカードを 1 枚抜き取り、任意の場所に挿入する。

山札の上から下に向けて、カードを昇順に並べ替えるために必要な、最小の操作回数を求めてください。

入力

入力は以下の形式で標準入力から与えられる。 
N
c_1
c_2
:
c_N
  1. 1 行目にはカードの枚数を示す整数 N(1≦N≦3 \times 10^4) が与えられる。
  2. 2 行目からは N 行にわたって、山札の初期状態が与えられる。
    • c_i は山札の上から i 番目にあるカードを示す整数で、1≦c_i≦N を満たす。
      • c_1 が山札の一番上にあるカードで、c_N が山札の一番下にあるカードを示す。
    • i \neq j ならば c_i \neq c_j である。つまり、N 枚のカードは全て異なる数字が書かれている。

出力

山札の上から下に向けて、カードを昇順に並べ替えるために必要な、最小の操作回数を求めてください。

また、出力の末尾には改行を入れること。

部分点

この問題には 3 つのデータセットがあり、データセット毎に部分点が設定されている。

  • N(1≦N≦16) を満たすデータセット全てに正解すると、10 点が与えられる。
  • N(1≦N≦1,000) を満たすデータセット全てに正解すると、上記のデータセットとは別に 40 点が与えられる。
  • 全てのデータセットに正解すると、100 点が与えられる。

入力例 1

6
1
3
5
2
4
6

出力例 1

2
  • 2 を抜いて 1 と 3 の間に入れます。
  • 5 を抜いて 4 と 6 の間に入れます。

入力例 2

5
5
4
3
2
1

出力例 2

4

入力例 3

7
1
2
3
4
5
6
7

出力例 3

0