题目描述

列车按给定顺序从入口驶入若干条平行轨道。每条轨道先进先出，列车不能超车。可以交替选择各轨道的队首列车从出口离开，要求离开顺序为编号从大到小。求至少需要多少条平行轨道。

输入格式

第一行 $N$，第二行1至 $N$ 的一个排列，表示进入顺序。

输出格式

输出最少轨道数。

样例

9
8 4 2 5 3 9 1 6 7

4

数据范围

$2\le N\le10^5$。