Bartek は著名なテクノ音楽プロデューサーであり、現在次のヒット曲を仕上げているところです。彼は $1$ から $n$ まで連続して番号が付けられた $n$ 個のビートからなるトラックを作成しました。音楽編集プログラムで何時間も作業した後、mp3 ファイルを書き出そうとしたところで、現在ビートが $a_1, a_2, \dots, a_n$ の順に並んでいることに気づきました。Bartek はビートを昇順、すなわち $1, 2, \dots, n$ の順にする必要があります。

このプログラムでは、次の 2 種類の操作が可能です：

• 最後のビートを任意の位置に移動する。例：$(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$。
• 任意のビートを先頭に移動する。例：$(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$。

ビートを昇順に並べるために必要な最小の操作回数はいくつですか？

入力

1 行目には、ビートの個数を表す整数 $n$ ($1 \le n \le 200\,000$) が含まれます。

2 行目には、プログラム内の現在のビートの順序を表す、互いに異なる $n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$) が含まれます。

出力

必要な最小の操作回数を表す 1 つの整数を出力してください。

入出力例

入力 1

6
3 2 5 4 1 6

出力 1

4

入力 2

9
3 1 2 5 6 4 9 7 8

出力 2

6

注記

ビートの列 $(3, 2, 5, 4, 1, 6)$ から始めます。4 回の操作で目的の順序を達成する 1 つの方法は以下の通りです：

• 最後のビートを左に 2 つ移動する：$(3, 2, 5, \underline{6}, 4, 1)$。
• ビート $2$ を先頭に移動する：$(\underline{2}, 3, 5, 6, 4, 1)$。
• ビート $1$ を先頭に移動する：$(\underline{1}, 2, 3, 5, 6, 4)$。
• 最後のビートを左に 2 つ移動する：$(1, 2, 3, \underline{4}, 5, 6)$。

4 回の操作で昇順を得る他の方法もありますが、3 回の操作で行うことはできないため、答えは $4$ です。