Longest Increasing Subsequence

Given an array of integers, find the length of the longest strictly increasing subsequence. 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.

Your task is to compute the length of this subsequence. The subsequence does not have to be contiguous.

Recall that a subsequence \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\) is strictly increasing if \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\), where \(1 \leq i_1 < i_2 < \cdots < i_k \leq n\).

inputFormat

The first line contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

Output a single integer, the length of the longest strictly increasing subsequence.

8
10 9 2 5 3 7 101 18

4