题目描述

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

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

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

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行一个整数 $A_i$。

$1 \le N \le 10^5$，$0 \le A_i \le 10^9$。

输出格式

满足条件的最小颜色数。

5
2
1
4
5
3

2

4
0
0
0
0

4