Son Halo 拥有 $n$ 艘编号为 $1$ 到 $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 认为，当线段 $[x_i^{min}, x_i^{max}]$ 和 $[x_j^{min}, x_j^{max}]$ 拥有公共内点，但其中任何一个线段都没有完全包含在另一个线段中时，绳子 $i$ 和绳子 $j$ 发生交叉。其中 $x_k^{min} = \min(x_{k-1}, x_k)$，$x_k^{max} = \max(x_{k-1}, x_k)$。即： $$x_i^{min} < x_j^{min} < x_i^{max} < x_j^{max}$$ 或者 $$x_j^{min} < x_i^{min} < x_j^{max} < x_i^{max}$$

Son Halo 想要重新排列这些飞船，使得没有任何绳子交叉。由于他很懒，他希望在重新排列后，保持在原始位置 $x_i$ 的飞船总数尽可能多。所有飞船在重新排列后必须保持在空间站的同一侧，且位于不同的位置 $x_i$。不过，重新排列后飞船可以占据任何实数位置 $x_i$。

你的任务是计算出最多有多少艘飞船可以保持在它们最初的位置。

输入格式

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

输出格式

输出文件必须包含一个整数，表示在该问题中能够保持在初始位置的飞船的最大数量。

样例

样例输入 1

4
1 3 2 4

样例输出 1

3

样例输入 2

4
1 4 2 3

样例输出 2

4

说明

在第一个样例中，Son Halo 可以将第二艘飞船移动到第一艘和第三艘之间的位置，从而在保持其他 3 艘飞船在初始位置的同时解决问题。

在第二个样例中，不存在绳子交叉，因此所有 4 艘飞船都可以留在它们的初始位置。