Zigzag Histogram Partition

A histogram is formed by placing $N$ rectangles of width $1$ and heights $h_1$, $\cdots$, $h_N$ in order.

You cut the histogram into several pieces by slicing perpendicular to the base. Each piece must have a positive integer width. When the pieces are listed in order, the largest rectangle area fully contained in each piece forms a zigzag sequence. Maximize the number of pieces.

Formally, a sequence $[a_1, \cdots, a_n]$ is a zigzag sequence if it satisfies at least one of the following two conditions.

• For every $1 \leq i < n$, if $i$ is even then $a_i \leq a_{i+1}$, and if $i$ is odd then $a_i \geq a_{i+1}$.
• For every $1 \leq i < n$, if $i$ is even then $a_i \geq a_{i+1}$, and if $i$ is odd then $a_i \leq a_{i+1}$.

You can transform the histogram with the following operation.

• Take a strictly increasing sequence $[a_1, a_2, \cdots, a_{k+1}]$ with $a_1 = 0$ and $a_{k+1} = N$.
• The result is a sequence of length $k$, written $[b_1, \cdots, b_k]$.
• For every $1 \leq i \leq k$, $b_i$ is the largest rectangle area in the histogram formed by joining rectangles $a_i+1$ through $a_{i+1}$ in order.

For every valid sequence $[a_1, \cdots, a_{k+1}]$, take the resulting sequence $[b_1, \cdots, b_k]$. Find the length of the longest one that is a zigzag sequence.

The first line contains a positive integer $N$ ($1 \le N \le 500\,000$).

The second line contains $N$ positive integers $h_1, \cdots, h_N$ separated by spaces ($1 \le h_i \le 10^{9}$).

Print the answer on the first line.