Longest Increasing Subsequence

You are given a sequence of integers representing the beauty values of different flowers. Your task is to compute the length of the longest strictly increasing subsequence (LIS) in the sequence. A subsequence is a sequence derived from the original sequence by deleting some or no elements without changing the order of the remaining elements. This problem can be solved efficiently in (O(N \log N)) time using dynamic programming combined with binary search.

For example, given the sequence [10, 22, 9, 33, 21, 50, 41, 60], the longest strictly increasing subsequence is [10, 22, 33, 50, 60] with a length of 5.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains an integer (N), representing the number of flowers.
2. The second line contains (N) space-separated integers, where each integer represents the beauty value of a flower.

If (N = 0), the second line will be empty.

outputFormat

Output a single integer to standard output (stdout) — the length of the longest strictly increasing subsequence.## sample

8
10 22 9 33 21 50 41 60

5