当前没有测试数据。

题目描述

给你一个长度为 𝑁N 的整数序列：𝐴={𝐴1,𝐴2,𝐴3,⋯ ,𝐴𝑁}A={A1​**,A2​,A3​,⋯,AN​}，对于 𝑁N** 个整数，我们可以为每一个整数涂上颜色。但要求满足下面这个条件：

如果 𝐴𝑖Ai​ 与 𝐴𝑗Aj​ 被涂上同一种颜色，那一定满足 𝐴𝑖<𝐴𝑗Ai​<Aj​（𝑖<𝑗i<j）。

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

输入格式

第一行输入𝑁N

第二行输入𝐴1A1​ 至 𝐴𝑁AN​

输出格式

为满足条件而上色时，输出所使用颜色数量的最小值。

输入数据 1

5
2
1
4
5
3

Copy

输出数据 1

2

Copy

输入数据 2

4
0
0
0
0

Copy

输出数据 2

4

Copy

提示

数据范围

• 1≤𝑁≤1051 ≤ N ≤ 105
• 0≤𝐴𝑖≤1090 ≤ Ai​ ≤ 109