#503. 序列

序列

题目描述

有 𝑛𝑛 个不相同的整数组成的数列,记为: 𝑎(1), 𝑎(2), … … , 𝑎(𝑛),例如: 3, 18, 7,14, 10, 12, 23, 41, 16, 24。 上例中挑出: 3, 18, 23, 24就是一个长度为4的上升序列,如果挑出: 3, 7, 10, 12, 16, 24长度为6的上升序列。求出最长的上升序列的长度。

输入格式

第一行一个整数𝑛𝑛(1 <= 𝑛 <= 1000) 第二行为 𝑛 个空格隔开的整数。

输出格式

最长上升子序列的长度。

样例

输入样例

10
3 18 7 14 10 12 23 41 16 24

输出样例

6

数据范围与提示

10%数据,如样例所述; 数据点2中,输入的20个整数严格上升; 数据点3中,输入的20个整数严格下降; 数据点4中,输入的1000个整数相等; 数据点5中, 𝑛 <= 10; 数据点6~10无特殊限制, 1 <= 𝑛 <= 1000。