Description

大家还记不记得苏伊士运河赌船事件:一艘大型集装箱货船以一己之力,切断全球经济大动脉,堵塞了300多条船,可以说是世界上最昂贵的意外qaq!

时刻关注国家大事的LHY就在思考了,为什么不多建几个运河!(呵呵了);

同时LHY在想被堵的船只肯定有着需急速通过运河的和不是很着急的!并按照着忙程度给船只们编了个号,注意船只被赌时是乱序的,但通过运河时只能是号码大的先通过(即需急速通过运河的先走)。

请聪明的你帮LHY算一算至少需要多少个运河,才能满足这个条件!

如图:

Format

Input

第一行输入一个整数N(2<=N<=1e5),下一行给出N个数

Output

输出至少需要的运河数量

Samples

9
8 4 2 5 3 9 1 6 7

4

Hint