题目描述

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

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

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

输入格式

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

$N$ $P_1$ $:$ $P_N$

输出格式

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

题目大意

给定一个 $1$ 到 $N$ 的排列，通过不断选择该序列中的元素，并将其放到序列的开头或末尾来对其进行排序，求最少需要几次这样的操作才能使得序列有序。可以证明总能通过进行这种操作将排列排序。
$1\le N\le 2\times 10^5$

4
1
3
2
4

2

6
3
2
5
1
4
6

4

8
6
3
1
2
7
4
8
5

5

提示

制約

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

Sample Explanation 1

例えば、以下の操作によって列を昇順に並び替えることができます。 - $2$ を先頭に移動する。新しい数列は $(2,1,3,4)$ となる。 - $1$ を先頭に移動する。新しい数列は $(1,2,3,4)$ となる。