ICPC NEERC 2014 I - Improvements

View as PDF

Submit solution


Points: 15
Time limit: 2.0s
Memory limit: 1G

Problem type

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. The 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^{min}_i, x^{max}_i] and [x^{min}_j, x^{max}_j] have common internal point but neither one of them is completely contained in the other, where x^{min}_k = \min (x_{k-1}, x_k), x^{max}_k = \max (x_{k-1}, x_k). That is:

\displaystyle \begin{cases}
x^{min}_i < x^{min}_j \text{ and } x^{min}_j < x^{max}_i \text{ and } x^{max}_i < x^{max}_j \\
x^{min}_j < x^{min}_i \text{ and } x^{min}_i < x^{max}_j \text{ and } x^{max}_j < x^{max}_i
\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.

Input Specification

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.

Output Specification

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.

Sample Input 1

4
1 3 2 4

Sample Output 1

3

Sample Input 2

4
1 4 2 3

Sample Output 2

4

Note

In the first sample, Son Halo can move the second spaceship in the position between the first and the third to solve the problem while keeping 3 other ships at their initial positions.

In the second sample, there are no rope intersections, so all 4 ships can be left at their initial positions.

Creative Commons Attribution 3.0 Unported

Comments

There are no comments at the moment.