시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB57282450.000%

## 문제

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.