Longest Increasing Subsequence

Given a sequence of cards represented by integers, your task is to compute the length of the longest strictly increasing subsequence. A subsequence is derived from the original sequence by deleting some or no elements without changing the order of the remaining elements.

The problem can be formalized as finding the maximum k such that there exists indices \(1 \le i_1 < i_2 < \cdots < i_k \le n\) for which

[ cards[i_1] < cards[i_2] < \cdots < cards[i_k] ]

For example, given the sequence [10, 22, 9, 33, 21, 50, 41, 60, 80], the longest strictly increasing subsequence is [10, 22, 33, 50, 60, 80], so the answer is 6.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

1. The first line contains a single integer n which denotes the number of cards (0 ≤ n ≤ 10⁵).
2. The second line contains n space-separated integers representing the card values.

If n is 0, the second line will be empty.

outputFormat

Output a single integer to standard output (stdout), which is the length of the longest strictly increasing subsequence of the given card values.

9
10 22 9 33 21 50 41 60 80

6