サイズ $N$ の整数配列 $A$ に対して、シャッフル操作を以下のように定義します。

• 最初に、空の整数配列 $B$ を作成します。
• 次に、$A$ が空になるまで、$A$ の左端または右端の要素を取り出し、その値を $B$ の末尾に追加します。
• $A$ が空になったら、$A$ を $B$ に置き換えて終了します。

シャッフル操作が上の図のように行われる場合、配列 $A$ の値は次のように変化します。

$(34, 19, 5, 36, 4, 25, 12, 9) \to (9, 34, 19, 12, 25, 4, 5, 36)$

配列 $A$ の $i$ 番目の要素を $A_i$ とします。$1 \le i < j \le N$ ならば $A_i \le A_j$ という条件が成り立つとき、配列 $A$ は単調増加であると言います。

サイズ $N$ の整数配列 $A$ が与えられたとき、配列 $A$ を単調増加にするために必要なシャッフル操作の最小回数を求めるプログラムを作成してください。

入力

入力の最初の行には、配列 $A$ の要素数 $N$ ($1 \le N \le 3 \cdot 10^5$) が含まれます。 2行目には、$N$ 個の整数 $A_1, \dots, A_N$ が含まれます（$1 \le A_i \le 10^9$）。

出力

配列 $A$ を単調増加にするために必要なシャッフル操作の最小回数を出力してください。

入出力例

入力 1

3
2 2 5

出力 1

0

入力 2

6
1 5 8 10 3 2

出力 2

1