Problem E
Zip Lines

When living in the Swiss alps, there isn’t much to do except eating chocolate, keeping great track of the time and skiing. That is, until you had the great idea of constructing an amazing zip line system for a new, exhilarating activity for Swiss daredevils.

We can model a segment of the Swiss alps as a series of points of heights $H_1, H_2, \dots , H_ N$. A single zip line is built by drawing a cable from one point $i$ of the alps to another point $j$, in such a way that the heights of all points $i+1, i+2, \dots , j-2, j-1$ are strictly less than both $H_ i$ and $H_ j$. Otherwise, you might accidentally crash into an alp top when using the zipline!

To build a zip line system, you want to select some points $a_1, a_2, \dots , a_ K$ such that $H_{a_1} > H_{a_2} > \dots > H_{a_ K - 1} > H_{a_ K}$, and you can build a zip line between points $a_ l$ and $a_{l + 1}$. In other words, a zip line system is a series of zip lines that always take you to a lower point in the alps.

In order to attract as many tourists to your future zip line system as possible, you want it to consist of as many zip lines as possible. Given the heights of all the points in the alp segment you want to build the system in, what’s the maximum number of zip lines the system can consist of?

Input

The first line of the input contains the integer $N$ ($1 \le N \le 200\, 000$), the number of points on the alp segment.

The next line contains the $N$ integers $H_1, H_2, \dots , H_ N$ ($1 \le H_ i \le 10^9$), the heights of the points on the alp segment, in order from left to right.

Output

Output a single integer – the maximum number of zip lines you can build in a zip line system.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group.

5
1 2 3 4 5

4

5
3 6 1 2 4

3