题目描述

给定一个整数序列，求它的最长严格上升子序列的长度。 严格上升子序列的定义：从原序列中选取若干元素，不改变元素在原序列中的相对顺序，且后一个元素严格大于前一个元素。

输入格式

第一行：一个整数N，代表序列的长度，满足1 ≤ N ≤ 1000。 第二行：N个整数，每个数的取值范围为0到10000。

输出格式

输出一个整数，即最长严格上升子序列的长度。

输入输出样例

输入样例1

7
1 7 3 5 9 4 8

输出样例1

4

样例解释

输入的序列为：[1, 7, 3, 5, 9, 4, 8]

可以找到多个长度为4的严格上升子序列，例如：

• [1, 3, 5, 8]
• [1, 3, 5, 9]
• [1, 3, 4, 8]