시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 52 23 19 44.186%

## 문제

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 ≤ $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_{i}^{min}$, $x_{i}^{max}$] and [$x_{j}^{max}$, $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} ~ \& ~ x_{j}^{min} < x_{i}^{max} ~ \& ~ x_{i}^{max} < x_{j}^{max} \\ x_{j}^{min} < x_{i}^{min} ~ \& ~ x_{i}^{min} < x_{j}^{max} ~ \& ~ 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 ≤ $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


## 예제 출력 1

3


## 예제 입력 2

4
1 4 2 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.

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