Longest Increasing Path in a Sequence

You are given a sequence of N numbers representing the heights of trees arranged in a row. Your task is to determine the length of the longest subsequence (also known as the longest increasing path) such that the heights are in strictly increasing order.

This problem can be modeled as finding the length of the Longest Increasing Subsequence (LIS) of the given sequence.

Mathematical Formulation:

If the sequence is \(h_1, h_2, \ldots, h_N\), find the maximum \(k\) such that there exist indices \(i_1 < i_2 < \ldots < i_k\) with \(h_{i_1} < h_{i_2} < \cdots < h_{i_k}\).

The solution is expected to run efficiently even if \(N\) becomes large.

inputFormat

The first line of input contains a single integer N which denotes the number of trees. The second line contains N space-separated integers representing the heights of the trees.

outputFormat

Output a single integer which is the length of the longest strictly increasing subsequence of the tree heights.

## sample

5
10 20 10 30 20

3

</p>