序列分解

题目描述

给定由 $N$ 个整数组成的数列 $A = \{ A_1, A_2, \cdots, A_N \}$。

对这 $N$ 个整数分别选择 1 种颜色并涂上。此时必须满足以下条件:

• 若 $A_i$ 与 $A_j$ ($i \lt j$) 涂了同一种颜色,则必须满足 $A_i \lt A_j$

在满足条件地涂色时,求所用的颜色数量的最小值。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出在满足条件地涂色时,所用的颜色数量的最小值。

样例

5
2
1
4
5
3

2

例如,把 $2, 3$ 涂成红色、把 $1, 4, 5$ 涂成蓝色,就能用 2 种颜色满足条件。

4
0
0
0
0

4

只能把所有整数都涂成不同的颜色。

数据范围

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