题目描述

$N$ 個の整数からなる数列 $A\ =\ \{\ A_1,\ A_2,\ \cdots,\ A_N\ \}$ が与えられます。 $N$ 個それぞれの整数に対して、色を $1$ つ選んでその色を塗ります。 この時、以下の条件を満たす必要があります:

• $A_i$ と $A_j\ (i\ <\ j)$ が同じ色で塗られているならば $A_i\ <\ A_j$ が成立する

条件を満たすように色を塗る時、用いる色の数の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

条件を満たすように色を塗る時、用いる色の数の最小値を出力せよ。

题目大意

给你一个长度为 $N$ 的整数序列：$A=\{A_1,A_2,A_3,\cdots,A_N\}$，对于 $N$ 个整数，我们可以为每一个整数涂上颜色。但要求满足下面这个条件：

如果 $A_i$ 与 $A_j$ 被涂上同一种颜色，那一定满足 $A_i < A_j$。

找到满足上述条件的最小颜色数。

By $\texttt{\color{black}Coros-Trusds}$

5
2
1
4
5
3

2

4
0
0
0
0

4

提示

制約

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

Sample Explanation 1

例えば、$2,\ 3$ を赤色、$1,\ 4,\ 5$ を青色で塗れば $2$ 色で条件を満たす塗り方が出来ます。

Sample Explanation 2

全ての整数を異なる色で塗るしかありません。