Longest Increasing Subsequence

You are given a sequence of integers. Your task is to compute the length of the longest strictly increasing subsequence in the sequence.

A subsequence is a sequence that can be derived from the original sequence by deleting some or no elements without changing the order of the remaining elements.

The expected time complexity is \(O(n \log n)\). For example, for the sequence \( [10, 22, 9, 33, 21, 50, 41, 60] \), the longest increasing subsequence is of length \(5\) (e.g. \( [10, 22, 33, 50, 60] \)).

inputFormat

The input begins with a single integer \(n\) (\(0 \le n \le 10^5\)), representing the number of elements in the sequence. The next line contains \(n\) space-separated integers.

outputFormat

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

## sample

8
10 22 9 33 21 50 41 60

5

</p>