配点 : $500$ 点

問題文

$1$ 以上 $N$ 以下の整数を並び替えてできる数列 $(P_1,P_2,...,P_N)$ が与えられます。 次の操作を繰り返してこの列を昇順に並び替えるとき、操作の回数の最小値を求めてください。

• 数列の要素を $1$ つ選び、その要素を列の先頭または末尾のうち好きなほうに移動する

なお、この操作によって与えられた列を昇順に並び替えられることは証明できます。

制約

• $1 \leq N \leq 2\times 10^5$
• $(P_1,P_2,...,P_N)$ は $(1,2,...,N)$ の並び替えである
• 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$

$P_1$

$:$

$P_N$

出力

操作の回数の最小値を出力せよ。

4
1
3
2
4

2

例えば、以下の操作によって列を昇順に並び替えることができます。

• $2$ を先頭に移動する。新しい数列は $(2,1,3,4)$ となる。
• $1$ を先頭に移動する。新しい数列は $(1,2,3,4)$ となる。

6
3
2
5
1
4
6

4

8
6
3
1
2
7
4
8
5

5