チューブの中に $N$ 個の玉が詰まっています。玉にはそれぞれ $1$ から $N$ の番号が割り当てられており、チューブの左端にあるものから順番に $A_1,A_2,\cdots ,A_N$ とします。ここで、このチューブに対して以下の操作を施していきます。

• チューブ内でもっとも番号の小さい玉が端(左右を問わない)にあるとき、これを石に変える
• チューブの左端から玉or石を $1$ つ取り出し、右端へ入れる
• チューブの右端から玉or石を $1$ つ取り出し、左端へ入れる

チューブ内のすべての玉を石に変えるのに必要な操作回数の最小値を求めてください。

• $1\leq N \leq 150000$
• $1\leq A_i \leq N$
• $A$ は $1$ から $N$ までの整数を並び替えた順列
• 入力はすべて整数です

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

$N$  
$A_1\quad A_2\quad \cdots A_N$

チューブ内のすべての玉を石に変えるのに必要な操作回数の最小値を出力してください。