Description

货物调度所用的传送带如下图所示

左端为传送带入口、右端为传送带出口，它们之间有 N​​ 条平行的传送带。每件货物从入口进入，选择任意一条传送带进入，最后从出口离开。图中有 9 件货物，在入口按照 {8,4,2,5,3,9,1,6}​ 的顺序排队等待进入。要求货物必须按照标号递减的顺序从出口离开，则至少需要多少条传送带？

Input Format

第一行给出一个整数 N(2 ≤ N ≤ 10^5)

第二行给出 1 到 N 的整数标号的重排列，数字以空格为间隔

Output Format

一行一个整数，为货物按照标号递减顺序从出口离开所需的最少的传送带的数量

9
8 4 2 5 3 9 1 6 7​

4​

Source

二分查找