Longest Increasing Subsequence

Given a sequence of integers, your task is to determine the length of the longest strictly increasing subsequence. A subsequence is derived from the original sequence by removing some or no elements without changing the order of the remaining elements. In particular, for a subsequence \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\), it must hold that \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\).

Note: A single element is considered as an increasing subsequence of length 1. If the sequence is empty, the answer is 0.

inputFormat

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

• The first line contains a single integer \(n\) (\(n \ge 0\)), representing the number of elements in the sequence.
• If \(n > 0\), the second line contains \(n\) space-separated integers.

If \(n = 0\), there will be no second line.

outputFormat

Output a single integer to standard output, which is the length of the longest strictly increasing subsequence.

8
10 22 9 33 21 50 41 60

5