Longest Increasing Subsequence

You are given an array of integers. Your task is to determine the length of the longest strictly increasing subsequence 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.

Formally, given an array \(a = (a_1,a_2,\dots,a_n)\), find the maximum integer \(k\) such that there exists indices \(1 \le i_1 < i_2 < \dots < i_k \le n\) with \[ a_{i_1} < a_{i_2} < \dots < a_{i_k} \]

Note: The subsequence does not need to be contiguous.

inputFormat

The first line contains an integer \(n\) representing 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 strictly increasing subsequence.

8
10 9 2 5 3 7 101 18

4