E - 序列分解

分数：500

问题描述

给定一个有 $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$

输出

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

5
2
1
4
5
3

2

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

4
0
0
0
0

4

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