Maximum Fixed Spaceships with Non-Intersecting Ropes

Son Halo has n spaceships numbered from 1 to n and a space station (numbered 0) located at position 0. The spaceship i is initially placed at position \(x_i\) (in meters) on the same side of the station so that \(x_i > 0\) and all \(x_i\) are distinct. Every two consecutive objects (the station and spaceship 1, and spaceship \(i-1\) and spaceship \(i\) for \(2 \le i \le n\)) are connected by a rope. In other words, rope \(i\) connects positions \(x_{i-1}\) and \(x_i\) with \(x_0 = 0\).

The rope between positions \(x_{i-1}\) and \(x_i\) is defined as the segment \([\min(x_{i-1}, x_i),\; \max(x_{i-1}, x_i)]\). Son Halo says that two ropes \(i\) and \(j\) (with \(i \neq j\)) intersect if:

[ \begin{cases} x_{i}^{\text{min}} < x_{j}^{\text{min}}; & ; x_{j}^{\text{min}} < x_{i}^{\text{max}}; & ; x_{i}^{\text{max}} < x_{j}^{\text{max}} \ x_{j}^{\text{min}} < x_{i}^{\text{min}}; & ; x_{i}^{\text{min}} < x_{j}^{\text{max}}; & ; x_{j}^{\text{max}} < x_{i}^{\text{max}} \end{cases} ]

He wishes to rearrange the spaceships such that no two ropes intersect and maximizes the number of spaceships that remain at their original positions. After rearrangement, all spaceships must be positioned at distinct positive positions and can be placed arbitrarily. Note that the connections (ropes) remain between spaceship \(i-1\) and spaceship \(i\) (with the station considered as spaceship 0 at position 0).

It can be proven that in order to avoid any rope intersections, the final positions must be arranged in strictly increasing order \(y_0=0, y_1, y_2, \dots, y_n\) (since if \(y_1 < y_2 < \cdots \lt; y_n\), each rope is simply \([y_{i-1}, y_i]\) and no two such segments intersect except possibly at endpoints).

Thus, if spaceship \(i\) remains fixed with \(y_i=x_i\), then for any two fixed spaceships \(i \lt j\), we must have \(x_i < x_j\). In other words, the set of ships that remain must form an increasing subsequence with respect to their initial positions.

Your task is to compute the maximal number of spaceships that can remain at their original positions. This is equivalent to finding the length of the longest increasing subsequence (LIS) of the given sequence \(x_1, x_2, \dots, x_n\).

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of spaceships.

The second line contains \(n\) distinct positive real numbers \(x_1, x_2, \dots, x_n\) separated by spaces, representing the initial positions of the spaceships.

outputFormat

Output a single integer: the maximal number of spaceships that can remain at their initial positions such that the ropes (after suitably rearranging the others) do not intersect.

sample

5
1 2 3 4 5

5