Longest Increasing Subsequence

Input & Output

Input

nums — the integer sequence

Output

the length of longest increasing subsequence

Example

Input

nums = [50, 3, 10, 7, 40, 80]

Output

Explanation

The longest increasing subsequence is [3, 7, 40, 80] which has length 4.

Example

Input

nums = [1, 2, 4, 3]

Output

Explanation

Both [1, 2, 4] and [1, 2, 3] are longest increasing subsequences which have length 3.

Try it yourself