题目描述

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.

题目大意

一个数轴上有 $n$ 个位置互异的点，第 $i$ 个点的坐标为 $x_i\ (x_i \gt 0)$，第 $i$ 个点和第 $i - 1$ 个点连了一根绳子（第 $1$ 个点和原点连了根绳子）定义两根绳子有交当且仅当它们跨越的区间有交且不是包含关系。你可以改变若干个点的坐标到一个任意的正实数位置，使得最后不存在任何两根绳子有交。最大化不动的点的个数。

$n\le 2\times 10^5$，$x_i$ 构成一个 $1,2,\cdots,n$ 的排列。

4
1 3 2 4

3

4
1 4 2 3

4

提示

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