Longest Increasing Subsequence

You are given a sequence of integers representing the heights of trees arranged in a row. Your task is to determine the length of the longest strictly increasing subsequence (LIS) in this sequence.

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting some elements without changing the order of the remaining elements. In this problem, the subsequence must be strictly increasing, that is, for any two consecutive elements \(a\) and \(b\) in the subsequence, \(a < b\) must hold.

The problem can be mathematically described as computing:

\[ LIS = \max_{1 \leq i \leq n} dp(i) \]

where \(dp(i)\) represents the length of the longest increasing subsequence ending at the \(i\)-th element.

Input is provided from stdin and output should be printed to stdout.

inputFormat

The first line contains an integer \(n\) representing the number of trees.

The second line contains \(n\) space-separated integers, where each integer represents the height of a tree.

outputFormat

Output a single integer representing the length of the longest strictly increasing subsequence.

## sample

6
5 3 4 8 6 7

4