給定一個大小為 $N$ 的整數陣列 $A$，洗牌（shuffle）操作定義如下：

• 最初，建立一個空的整數陣列 $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$ 變為單調遞增所需的最少洗牌操作次數。

輸入格式

第一行包含一個整數 $N$，代表陣列 $A$ 的元素個數 ($1 \le N \le 3 \cdot 10^5$)。 第二行包含 $N$ 個整數 $A_1, \dots, A_N$：陣列 $A$ 的初始值 ($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