1455 - 最长递增子序列的个数

通过次数

3

提交次数

5

Time Limit : 1 秒
Memory Limit : 128 MB

给定一个未排序的整数数组 nums , 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

Input

第一行为一个整数n

第二行为n个整数

Output

最长递增子序列的个数

Examples

Input

5
1 3 5 4 7

Output

2

Input

5
2 2 2 2 2

Output

5

Hint

1 <= nums.length <= 2000

-10^6 <= nums[i] <= 10^6