Longest Increasing Subsequence Length

Given an array of integers, your task is to determine the length of the longest strictly increasing subsequence (LIS) in the array.

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

The well-known efficient solution uses a greedy algorithm combined with binary search. For an array \(a_1, a_2, \ldots, a_n\), the algorithm maintains an auxiliary array where each element represents the smallest possible tail value for an increasing subsequence of a given length. The update step uses \(\text{bisect_left}\) (or its equivalent) to find the appropriate position in the auxiliary array.

Your solution must read the input from stdin and output the answer to stdout.

inputFormat

The first line contains an integer \(n\) (\(0 \le n \le 10^5\)), the number of elements in the array.

The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer representing the length of the longest increasing subsequence in the given array.

6
10 22 9 33 21 50

4