Longest Increasing Subsequence (LIS)

Given an array of integers, your task is to calculate the length of the longest increasing subsequence (LIS) in the array. An increasing subsequence is defined as a sequence of elements from the array (not necessarily contiguous) arranged in strictly increasing order.

The problem can be formally defined as: Given an array \(A = [a_1, a_2, \dots, a_n]\), find the maximum length \(L\) such that there exists a subsequence \(a_{i_1}, a_{i_2}, \dots, a_{i_L}\) with \(i_1 < i_2 < \cdots < i_L\) and \(a_{i_1} < a_{i_2} < \cdots < a_{i_L}\).

Example:

Input:
8
10 9 2 5 3 7 101 18
Output:
4

</p>

In the above example, one of the longest increasing subsequences is [2, 3, 7, 101].

inputFormat

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

If \(n = 0\), the array is empty.

outputFormat

Output a single integer which is the length of the longest increasing subsequence of the given array.

## sample

0

0

</p>