AT_abc006_4 [ABC006D] トランプ挿入ソート

[problemUrl]: https://atcoder.jp/contests/abc006/tasks/abc006_4 数字が書かれたカードが $ 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 $ 点が与えられる。 ```

6
1
3
5
2
4
6
```

 ```
2
```

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

 ```
4
```

 ```
7
1
2
3
4
5
6
7
```

 ```
0
```
                            

N/A

N/A