Longest Increasing Subsequence

You are given a sequence of integers. Your task is to compute the length of the longest subsequence such that the elements of the subsequence are in strictly increasing order. In other words, given a sequence \(a_1, a_2, \dots, a_n\), find the maximum length \(L\) for which there exists indices \(1 \leq i_1 < i_2 < \dots < i_L \leq n\) satisfying \(a_{i_1} < a_{i_2} < \dots < a_{i_L}\).

The expected solution should run efficiently for large inputs. A common approach is to use a method similar to patience sorting with binary search achieving a complexity of \(O(n \log n)\).

inputFormat

The first line of input contains a single integer \(n\) (where \(0 \leq n \leq 10^5\)), representing the number of elements in the sequence. The second line contains \(n\) space-separated integers.

outputFormat

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

6
5 2 8 6 3 6

3