Longest Increasing Subsequence

Karen has a garden with n plants, each having a specific height. She wishes to select a subsequence of these plants such that the heights of the selected plants are in strictly increasing order. Your task is to determine the maximum number of plants she can select under this condition.

Formally, given an array of integers representing the heights, find the length of the longest strictly increasing subsequence. Mathematically, if the heights are denoted by \( a_1, a_2, \ldots, a_n \), find the maximum length \( L \) such that there exists indices \( 1 \leq i_1 < i_2 < \ldots < i_L \leq n \) with \( a_{i_1} < a_{i_2} < \ldots < a_{i_L} \).

inputFormat

The first line contains an integer \( n \) (where \( n \geq 0 \)) indicating the number of plants. The second line contains \( n \) space-separated integers representing the heights of the plants. When \( n = 0 \), the second line is omitted.

outputFormat

Output a single integer representing the length of the longest strictly increasing subsequence of the given array of plant heights.

6
1 3 2 4 6 5

4