而这次，卡珊德拉复活到了现代，可是受传说的影响，卡珊德拉的预言不能完全被大众所接受。这次她带来了两组“半预言”，每组有n个“半预言”，，每一个“半预言”都有一个可信程度t(0≤t≤30000)。 如果上下两组分别选出两个半预言的可信程度相同，他们便可以合并为一个完整预言，完整预言的可信程度等于其中任意一个半预言。 补充一点，预言讲出的顺序不得混乱，所以每一个半预言的选取都必须严格按照卡珊德拉给出的顺序。 而如果讲出的后一个预言没有比前一个预言的可信程度高（即后必大于前），人们便不会再相信卡珊德拉的预言。

此时卡珊德拉希望讲出更多的预言，并且得到人们的信任，请问她最多能讲出多少个完整预言？

拿样例举例，第一组半预言为{1，4，2，6，8} 第二组半预言为{1，5，0，2，4} 其中能够合并为一个完整预言的有1，2，4这三个，但他们不能同时选择，若选择了1，则只能在2，4中选择一个，最多能讲出2个预言。 如果选择了4，则下一个只能选2，因为1的顺序更前。

输入描述

第一行，一个正整数n。 第二行，n个正整数，表示卡珊德拉带来的每个预言的可信度。

输出描述

一个整数，卡珊德拉最多能说出多少个预言？

用例输入 1

5 1 4 2 6 8 1 5 0 2 4

用例输出 1

2

提示

N≤5000