Longest Increasing Subsequence of Tree Heights

In this problem, you are given the heights of a row of trees. Your task is to determine the maximum number of trees that can be kept such that their heights form a strictly increasing sequence. Formally, given an array (a_1, a_2, \dots, a_n) representing the heights of trees, you need to compute the length of the longest subsequence (a_{i_1}, a_{i_2}, \dots, a_{i_k}) (with (1 \le i_1 < i_2 < \cdots < i_k \le n)) such that (a_{i_1} < a_{i_2} < \cdots < a_{i_k}).

The solution can be implemented using dynamic programming with a time complexity of (O(n^2)), which is efficient for moderate-sized input arrays.

Example: If the input is 7\n3 4 2 1 10 6 7, then the answer is 4 because one of the longest strictly increasing subsequences is [3, 4, 6, 7].

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a single integer (n) representing the number of trees.
• The second line contains (n) space-separated integers representing the heights of the trees. If (n) is 0, the second line may be empty.

outputFormat

Output a single integer to standard output (stdout) representing the length of the longest strictly increasing subsequence of tree heights.## sample

7
3 4 2 1 10 6 7

4