Maximum Trees in Increasing Sequence

You are given a sequence of integers representing the heights of trees. You have the option to cut some trees so that the remaining trees form a strictly increasing sequence. Your task is to determine the maximum number of trees that can remain such that their heights are in strictly increasing order.

Formally, given a sequence \(a_1, a_2, \ldots, a_n\), find the length of the longest subsequence \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\) with \(i_1 < i_2 < \cdots < i_k\) and \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\).

This is a classic Longest Increasing Subsequence (LIS) problem which can be solved efficiently using a greedy approach combined with binary search.

inputFormat

The first line contains an integer \(n\) representing the number of trees. The second line contains \(n\) space-separated integers representing the heights of the trees.

If \(n = 0\), there will be no second line and the answer is 0.

outputFormat

Output a single integer representing the maximum number of trees that can remain to form a strictly increasing sequence.

6
3 10 2 1 20 4

3