問題文

数字が書かれたカードが $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