Longest Increasing Subsequence

You are given a sequence of integers. Your task is to determine the length of the longest increasing subsequence (LIS) within 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. An increasing subsequence is one in which every element is strictly greater than its preceding element.

The classical problem of finding the LIS can be solved efficiently using a dynamic programming approach combined with binary search. In this problem, you should implement an algorithm with an expected time complexity of \(O(n \log n)\), where \(n\) is the number of elements in the sequence.

Note: If the input sequence is empty, output 0.

inputFormat

The input is provided in two lines:

• The first line contains a single integer \(n\) representing the number of elements in the sequence.
• The second line contains \(n\) space-separated integers which represent the sequence.

You may assume that \(0 \leq n \leq 10^5\) and each integer fits in a 32-bit signed integer.

outputFormat

Output a single integer which is the length of the longest strictly increasing subsequence of the given sequence.

## sample

8
5 2 8 6 3 6 9 7

4

</p>