畀出一個大小為 $N$ 嘅整數陣列 $A$，洗牌操作定義如下。

• 最初，建立一個空嘅整數陣列 $B$。
• 之後，只要 $A$ 仲未空，就移除 $A$ 最左邊或者最右邊嘅元素，再將個值加到 $B$ 嘅最右邊。
• 如果 $A$ 空咗，就用 $B$ 取代 $A$，然後停止。

如果按上圖進行洗牌操作，陣列 $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,\ldots,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