Longest Increasing Subsequence

Given an array A of n integers, your task is to determine the length of the longest strictly increasing subsequence (LIS) in the array.

An increasing subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements, and where each element is greater than its preceding element. For example, if A = [10, 9, 2, 5, 3, 7, 101, 18], one valid longest increasing subsequence is [2, 5, 7, 101], which has length 4.

You are required to read the input from standard input (stdin) and output your answer to standard output (stdout).

inputFormat

The input is given in two lines:

1. The first line contains a single integer n representing the number of elements in the array.
2. The second line contains n space-separated integers denoting the elements of the array. If n is 0, the second line will be omitted.

outputFormat

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

8
10 9 2 5 3 7 101 18

4