火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有 9 趟列车，在入口处按照 { 8，4，2，5，3，9，1，6，7 } 的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

时间限制：5000

内存限制：65536

输入

输入第一行给出一个整数 N (2 ≤ N ≤ 10⁵)，下一行给出从 1 到 N的整数序号的一个重排列。数字间以空格分隔。

输出

在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

样例输入

9
8 4 2 5 3 9 1 6 7

样例输出

4

{答案待计算}

这个问题是关于贪心算法的。我们需要确定在列车进站时如何有效地分配轨道，以便在出站时能够按照递减的顺序排列。贪心策略是优先选择序号较大的列车优先进入轨道，因为这样可以保证有更多的时间调整后续列车的顺序。因此，我们可以按照输入顺序的反序来安排列车进入轨道。由于出口轨道只有一个，我们需要确保任何时候都有足够的轨道供列车停放以便等待出口轨道上的列车离开。我们可以使用栈结构来模拟这个过程。每当我们有一个新列车进站时，我们将其放入栈顶，每次出口列车离开时，我们从栈顶取出一个列车。为了保证出口顺序递减，我们需要确保任何时候栈顶都是序号最大的列车。如果栈顶列车不满足出口顺序递减的条件，我们就需要清空栈中所有列车到新的轨道上重新安排。这样我们就需要更多的轨道来存储重新安排的列车直到它们满足出口顺序递减的条件。我们至少需要足够数量的轨道来存储所有等待出口轨道上列车的所有列车。因此，我们需要至少N条轨道来存储所有列车直到出口轨道上的列车离开。所以答案是输入序列的长度N。