题目描述

给定一个包含 $N$ 个整数的序列：$A = \\{ A_1, A_2, \\cdots, A_N \\}$。对于这 $N$ 个整数中的每一个，我们会选择一种颜色，并将整数涂上该颜色。需要满足以下条件：

• 如果 $A_i$ 和 $A_j$ $(i < j)$ 被涂上相同的颜色，那么 $A_i < A_j$。

找到满足条件的最少颜色数目。

约束条件

• $1 \\leq N \\leq 10^5$
• $0 \\leq A_i \\leq 10^9$

输入

输入数据从标准输入读入，数据格式如下：

$N$ $A_1$ $:$ $A_N$

输出

输出满足条件的最少颜色数目。

示例输入 1

5
2
1
4
5
3

示例输出 1

2

我们可以通过使用两种颜色来满足条件，例如将 $2$ 和 $3$ 涂成红色，将 $1$、$4$ 和 $5$ 涂成蓝色。

示例输入 2

4
0
0
0
0

示例输出 2

4

我们必须用不同的颜色来涂所有的整数。