题目描述

给定一个有 $N$ 个整数的序列:$A ={A_1,A_2,…,A_N}$。

对于这 $N$ 个整数中的每一个，我们会选择一种颜色并将该整数涂上这种颜色。

满足以下条件:

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

找出满足条件所需的最小颜色数。

输入

第一行一个整数$N$

接下来一共$N$行，第$i$个数表示序列的$A_i$。

输出

输出满足条件所需的最小颜色数。

5
2
1
4
5
3

2

样例解释

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

4
0
0
0
0

4

样例解释

我们必须使用不同的颜色为所有整数着色。

提示

$1 \leq N \leq 10^5$

$0 \leq A_i \leq 10^9$