分数: 500 点
问题陈述
给你一个序列 N 整数: A = \{ A_1, A_2, \cdots, A_N \}。 对于每一个 N 整数,我们将选择一种颜色并用该颜色绘制整数。这里必须满足以下条件:
- If 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
输出
打印满足条件所需的最少颜色数。
示例输入 1
5 2 1 4 5 3
示例输出 1
2
我们可以通过例如绘画来满足两种颜色的条件 2 和 3 红色和绘画 1, 4,和 5 蓝色。
示例输入 2
4 0 0 0 0
示例输出 2
4
我们必须用不同的颜色绘制所有整数。