Longest Increasing Subsequence

Given an array of integers, you are required to compute the length of the longest strictly increasing subsequence. A subsequence is a sequence derived from the array by deleting some or no elements without changing the order of the remaining elements. The solution must work in O(n log n) time complexity. For example, if the input array is [10, 9, 2, 5, 3, 7], one of the longest strictly increasing subsequences is [2, 5, 7] and its length is 3.

The task is to implement a program that reads from standard input and writes the result to standard output. Use appropriate algorithms and data structures to ensure efficiency, especially for large inputs.

inputFormat

The first line of input contains an integer n (0 ≤ n ≤ 10^5) representing the number of elements in the array. The second line contains n space-separated integers, which are the elements of the array. If n is 0, the second line will be empty.

outputFormat

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

6
10 9 2 5 3 7

3