Longest Increasing Subsequence

Given an array of integers, your task is to find the length of the longest strictly increasing subsequence (LIS) in the array. A subsequence is a sequence that can be derived from the array by removing some or no elements without changing the order of the remaining elements. Formally, for an array A of size n, a subsequence is a sequence A[i₁], A[i₂], ..., A[i_k] with \(1 \le i_1 < i_2 < \cdots < i_k \le n\). The strictly increasing subsequence requires that each element is less than its following element.

Your goal is to compute the maximum possible length k such that the subsequence is strictly increasing.

inputFormat

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

1. The first line contains a single integer \(n\) representing the number of elements in the array. \(n\) can be 0.
2. The second line contains \(n\) space-separated integers representing the array elements. If \(n = 0\), the second line may be omitted.

outputFormat

Output a single integer to standard output representing the length of the longest strictly increasing subsequence.

8
10 9 2 5 3 7 101 18

4