P6993 [NEERC 2014] Improvements

Son Halo owns $n$ spaceships numbered from $1$ to $n$ and a space station. They are initially placed on one line with the space station so the spaceship $i$ is positioned $x_i$ meters from the station and all ships are on the same side from the station $(x_i > 0)$ . All $x_i$ are distinct. Station is considered to have number $0$ and $x_0$ is considered to be equal to $0$ . Every two spaceships with consequent numbers are connected by a rope, and the first one is connected to the station. The rope number $i$ (for $1 \le i \le n)$ connects ships $i$ and $i-1.$ Note, that the rope number $1$ connects the first ship to the station. Son Halo considers that the rope $i$ and the rope $j$ intersect when the segments $[x_{i}^{min}, x_{i}^{max}]$ and $[x_{j}^{min}, x_{j}^{max}]$ have common internal point but neither one of them is completely contained in the other, where $x_{k}^{min} = \min(x_{k−1}, x_k)$, $x_{k}^{max} = max(x_{k−1}, x_k).$ That is: $$\begin{cases} x_{i}^{min} < x_{j}^{min} \sim \& \sim x_{j}^{min} < x_{i}^{max} \sim \& \sim x_{i}^{max} < x_{j}^{max} \\ x_{j}^{min} < x_{i}^{min} \sim \& \sim x_{i}^{min} < x_{j}^{max} \sim \& \sim x_{j}^{max} < x_{i}^{max}  \end{cases}$$ Son Halo wants to rearrange spaceships in such a way, that there are no rope intersections. Because he is lazy, he wants to rearrange the ships in such a way, that the total number of ships that remain at their original position $x_i$ is maximal. All the ships must stay on the same side of the station and at different positions $x_i$ after rearrangement. However, ships can occupy any real positions $x_i$ after rearrangement. Your task is to figure out what is the maximal number of ships that can remain at their initial positions.

The first line of the input file contains $\(n\) (1 \le \(n\) \le 200 000)$ -- the number of ships. The following line contains $\(n\)$ distinct integers $\(x_i\) (1 \le \(x_i\) \le \(n\))$ -- the initial positions of the spaceships.

The output file must contain one integer -- the maximal number of ships that can remain at their initial positions in the solution of this problem.

Time limit: 1 s, Memory limit: 256 MB.