Longest Increasing Subsequence

Given an array of integers, your task is to compute the length of the longest strictly increasing subsequence (LIS) within the array. A subsequence is a sequence derived from the array by deleting some or no elements without changing the order of the remaining elements. For example, if the array is \( [10, 9, 2, 5, 3, 7, 101, 18] \), one of the longest increasing subsequences is \( [2, 3, 7, 101] \), so the answer is 4.

inputFormat

The first line of input 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 denoting the length of the longest increasing subsequence.

8
10 9 2 5 3 7 101 18

4