Longest Increasing Subsequence

You are given an array of integers representing the heights of lanterns. Your task is to compute the length of the longest strictly increasing subsequence that can be formed from these heights.

A subsequence is obtained by removing zero or more elements from the array without changing the order of the remaining elements. Note that the subsequence must be strictly increasing, i.e., for any two consecutive elements a and b in the subsequence, it holds that \(a < b\).

This problem is a classical algorithm challenge which can be solved efficiently using dynamic programming combined with binary search.

inputFormat

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

outputFormat

Output a single integer representing the length of the longest strictly increasing subsequence composed of the lanterns' heights.

## sample

6
5 1 8 3 6 7

4

</p>