题目描述

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

输入格式

第一行：一个整数 $N$，代表序列的长度。
第二行：$N$ 个整数，表示序列的元素。

输出格式

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

样例

7
1 2 4 1 3 4 5

5

样例解释 输入的序列为 [1, 2, 4, 1, 3, 4, 5]。可以找到长度为5的严格上升子序列，例如选取第1、2、5、6、7个元素：[1, 2, 3, 4, 5]。

数据范围

• $1 \le N \le 10^5$
• $0 \le a_i \le 10^9$