题目描述

给你一个整数数组 $nums$，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，$[3,6,2,7]$ 是数组 $[0,3,1,6,2,2,7]$ 的子序列。

输入描述

输入一行整数 $nums_i(1\le n\le 2500, -10^4\le nums_i\le 10^4)$，表示数组元素，以空格分隔。

输出描述

输出一个整数，表示最长严格递增子序列的长度。

样例1

输入

10 9 2 5 3 7 101 18

输出

4

样例解释

最长递增子序列是 $[2,3,7,101]$，长度为 $4$。

样例2

输入

0 1 0 3 2 3

输出

4

样例解释

最长递增子序列是 $[0,1,2,3]$，长度为 $4$。

样例3

输入

7 7 7 7 7 7 7

输出

1

样例解释

所有元素相同，最长严格递增子序列长度为 $1$。