A scholarship committee reviews students in the order they applied. Each student has a skill score
The committee wants to select a chain of students such that their application order is preserved and each selected student's skill score is strictly greater than the previous selected student's score.
Find the maximum possible number of students in such a chain.
The hidden idea: instead of storing every chain, keep the smallest possible ending score for every chain length.
The first line contains an integer KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression.
Print a single integer — the length of the longest valid growth chain.
Input
6
10 20 10 30 20 504One valid chain is KaTeX can only parse string typed expression.
Example 2:
Input
5
5 4 3 2 11