Description

Son Halo 拥有编号从 1 到 $n$ 的 $n$ 艘飞船和一个空间站。它们最初与空间站在一条直线上排列，因此飞船 $i$ 距离空间站 $x_i$ 米，并且所有飞船都在空间站的同一侧（$x_i > 0$）。所有 $x_i$ 都是不同的。空间站被认为是编号为 0，并且 $x_0$ 被认为等于 0。

每两艘连续编号的飞船之间用绳子连接，第一艘飞船与空间站连接。编号为 $i$ 的绳子（对于 $1 \le i \le n$）连接飞船 $i$ 和 $i-1$。注意，编号为 1 的绳子连接第一艘飞船与空间站。

Son Halo 认为绳子 $i$ 和绳子 $j$ 相交，当且仅当线段 $[x_{i}^{min}, x_{i}^{max}]$ 和 $[x_{j}^{min}, x_{j}^{max}]$ 有公共的内部点，但它们中的任何一个都不完全包含在另一个中，其中 $x_{k}^{min} = \min(x_{k-1}, x_k)$，$x_{k}^{max} = \max(x_{k-1}, x_k)$。即：

$$\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 想要重新排列飞船，使得没有绳子相交。因为他很懒，他希望以一种方式重新排列飞船，使得保持在原始位置 $x_i$ 的飞船总数最大化。所有飞船在重新排列后必须保持在空间站的同一侧，并且在不同的位置 $x_i$。然而，飞船在重新排列后可以占据任何实数位置 $x_i$。

你的任务是找出可以保持在其初始位置的飞船的最大数量。

Input Format

输入文件的第一行包含 $n$ $(1 \le n \le 200\,000)$ —— 飞船的数量。接下来的行包含 $n$ 个不同的整数 $x_i$ $(1 \le x_i \le n)$ —— 飞船的初始位置。

Output Format

输出文件必须包含一个整数 —— 在该问题的解决方案中可以保持在其初始位置的飞船的最大数量。

4
1 3 2 4

3

4
1 4 2 3

4

Hint

时间限制：1 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。