AlanashKO 喜歡錢。新年前夕，他收到了 $N$ 張鈔票。每張鈔票的面額都是正整數。玩耍時，AlanashKO 把所有鈔票排成一列，從左到右編號為 $1$ 到 $N$。接著，他決定將所有鈔票按面額非遞減的順序排序。
為此，AlanashKO 執行以下程序：首先，將鈔票分成一個或多個互不重疊的連續子段，每張鈔票都屬於某個子段。接著，依照各子段原本由左到右的順序，依次將它們插入新的一列；也就是先插入最左邊的子段（第一個子段），再插入接下來最左邊的子段，依此類推。每個子段可以插在新列中任意兩張鈔票之間，也可以插在新列的任意一端。插入時，子段內鈔票的相對順序不變。
AlanashKO 想要在最終能將鈔票按非遞減順序排序的前提下，讓子段數最少。請幫他求出這個數值。
輸入格式
第一行包含一個正整數 $N$（$1 \le N \le 10^6$），表示鈔票數量。下一行包含 $N$ 個正整數 $a_i$（$1 \le a_i \le 10^6$），表示第 $i$ 張鈔票的面額。
輸出格式
在一行中輸出一個整數，表示能讓 AlanashKO 將鈔票排序所需的最少子段數。
子任務
本題包含四個子任務：
- $N \le 8$。9 分。
- $N \le 20$。16 分。
- $N \le 300$。20 分。
- $N \le 10^6$。55 分。
只有當解答成功通過之前的所有子任務時，才能獲得該子任務的分數。
範例
輸入格式 1
6 3 6 4 5 1 2
輸出格式 1
3
說明
子段是連續的序列。
考慮範例測試：
最少需要分成 3 個子段：$|3\ 6|4\ 5|1\ 2|$（豎線表示子段邊界）。
第一步之後，原列是 $|4\ 5|1\ 2|$，新列是 $|3\ 6|$。
第二步將子段 $|4\ 5|$ 插在 $3$ 和 $6$ 之間。
第二步之後，原列是 $|1\ 2|$，新列是 $|3\ 4\ 5\ 6|$。
最後，將子段 $|1\ 2|$ 插在新列開頭，得到 $|1\ 2\ 3\ 4\ 5\ 6|$。