题目描述

You are given a sequence with $N$ integers: $A = \{ A_1, A_2, \cdots, A_N \}$. For each of these $N$ integers, we will choose a color and paint the integer with that color. Here the following condition must be satisfied:

• If $A_i$ and $A_j$ $(i \lt j)$ are painted with the same color, $A_i \lt A_j$.

Find the minimum number of colors required to satisfy the condition.

给你一个包含 $N$ 个整数的序列： $A = \{ A_1, A_2, \cdots, A_N \}$ 。对于每一个 $N$ 整数，我们将选择一种颜色，并用这种颜色涂抹整数。这里必须满足以下条件：

• 如果 $A_i$ 和 $A_j$ 被涂成 $(i \lt j)$ 。 $(i \lt j)$ 涂上相同的颜色，即 $A_i \lt A_j$ 。

求满足条件所需的最少颜色数。

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印满足条件所需的最少颜色数。

样例 #1

样例输入 #1

5
2
1
4
5
3

样例输出 #1

2

样例 #2

样例输入 #2

4
0
0
0
0

样例输出 #2

4

说明

数据规模与约定

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

样例 $1$ 解释

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

样例 $2$ 解释

我们必须给所有整数涂上不同的颜色。