Longest Increasing Subsequence

You are given an integer array. Your task is to determine the length of the longest increasing subsequence (LIS) within the array.

An increasing subsequence is defined as a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements, and the resulting sequence is strictly increasing. Formally, given an array \( A = [a_1, a_2, \dots, a_n] \), you need to compute the maximum \( k \) such that there exists indices \(1 \leq i_1 < i_2 < \dots < i_k \leq n\) with \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\).

Example: For the array [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 input is given via standard input (stdin) and consists of two lines:

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

outputFormat

Output via standard output (stdout) a single integer which is the length of the longest increasing subsequence of the array.

## sample

8
10 9 2 5 3 7 101 18

4

</p>