Improvements

题号：NC54477
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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₀ 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 ≤ i ≤ 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})$ .

$\left[ \begin{array}{l} x^{min}_{i} < x^{min}_{j} \text{ \& } x^{min}_{j} < x^{max}_{i} \text{ \& } x^{max}_{i} < x^{max}_{j} \\ x^{min}_{j} < x^{min}_{i} \text{ \& } x^{min}_{i} < x^{max}_{j} \text{ \& } x^{max}_{j} < x^{max}_{i} \end{array} \right.$
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 ≤ n ≤ 200 000) — the number of ships. The following line contains n distinct integers x_i (1 ≤ x_i ≤ 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.

示例1

输入

复制

4
1 3 2 4

输出

复制

说明

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.

示例2

输入

复制

4
1 4 2 3

输出

复制

说明

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

备注:

Author: Vitaliy Aksenov