Question
Longest Increasing Subsequence Length
You are given an array of KaTeX can only parse string typed expression integers. Your task is to find the length of the Longest Increasing Subsequence (LIS) in the array.
A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. A subsequence is increasing if each element is strictly greater than the previous one.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the size of the array.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression — the elements of the array.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression — the elements of the array.
Output
Print a single integer — the length of the longest strictly increasing subsequence of the array.
Example
Input
8
10 9 2 5 3 7 101 18
Output
4
Explanation
One of the longest increasing subsequences is:
2 → 3 → 7 → 101
The length of this subsequence is 4.
8
10 9 2 5 3 7 101 18
Output
4
Explanation
One of the longest increasing subsequences is:
2 → 3 → 7 → 101
The length of this subsequence is 4.