Improvements

Son Halo owns $n$ spaceships, numbered from 1 to $n$, and one space station. The station and the ships all sit on a single line. Ship $i$ is $x_i$ meters from the station, and every $x_i$ is positive, so all ships are on the same side of the station. All $x_i$ are distinct. The station has number 0, and $x_0 = 0$.

Every two ships with consecutive numbers are joined by a rope, and the first ship is joined to the station. Rope $i$ (for $1 \le i \le n$) joins ship $i$ and ship $i-1$, so rope 1 joins the first ship to the station.

Write $x_k^{\min} = \min(x_{k-1}, x_k)$ and $x_k^{\max} = \max(x_{k-1}, x_k)$. Son Halo considers that rope $i$ and rope $j$ intersect when the segments $[x_i^{\min}, x_i^{\max}]$ and $[x_j^{\min}, x_j^{\max}]$ have a common interior point and neither segment is completely contained in the other, that is, when one of the following holds.

$\begin{cases} x_i^{\min} < x_j^{\min} < x_i^{\max} < x_j^{\max} \\ x_j^{\min} < x_i^{\min} < x_j^{\max} < x_i^{\max} \end{cases}$

Son Halo wants to rearrange the ships so that no two ropes intersect. He is lazy, so he wants the number of ships that remain at their original position $x_i$ to be as large as possible. After the rearrangement all ships must still be on the same side of the station and at distinct positions. A ship can be placed at any real position.

Find the largest number of ships that can remain at their initial positions.

The first line contains $n$ ($1 \le n \le 200\,000$), the number of ships. The second line contains $n$ distinct integers $x_i$ ($1 \le x_i \le n$), the initial positions of the ships.

Print one integer, the largest number of ships that can remain at their initial positions.

In the first example Son Halo can move the second ship to a position between the first ship and the third ship, and the other 3 ships keep their places. In the second example no two ropes intersect, so all 4 ships can stay where they are.