← 返回题目列表

AtCoder · abc134_e

E. 序列分解

中文机器翻译题面 查看原题

分数: 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

我们必须用不同的颜色绘制所有整数。