Longest Increasing Subsequence Length

Given an array of integers, your task is to determine the length of the longest increasing subsequence (LIS) in the array. An increasing subsequence is a sequence of numbers taken from the array (not necessarily contiguous) such that each number is larger than the previous one. The problem requires you to compute the length of the longest such subsequence.

More formally, given an array \(A = [a_1, a_2, \dots, a_n]\), find the length of the longest subsequence \(A' = [a_{i_1}, a_{i_2}, \dots, a_{i_k}]\) where \(1 \le i_1 < i_2 < \dots < i_k \le n\) and \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\). The classical dynamic programming or patience sorting algorithms can be used to solve this problem.

Input is read from standard input (stdin) and the output is written to standard output (stdout).

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) which represents the number of elements in the array. \(n\) can be 0.
• The second line contains \(n\) space-separated integers representing the elements of the array.

If \(n = 0\), the second line may be empty.

outputFormat

Output a single integer representing the length of the longest increasing subsequence in the array.

## sample

5
1 2 3 4 5

5

</p>