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|。