Longest Increasing Subsequence

You are given a sequence of n integers. Your task is to determine the length of the Longest Increasing Subsequence (LIS) in the sequence. An increasing subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order, and the elements in the subsequence are in strictly increasing order.

The problem can be formally defined as follows: given an array \(a = [a_1, a_2, \dots, a_n]\), find the length of the longest subsequence \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\) where \(1 \leq i_1 < i_2 < \dots < i_k \leq n\) and \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\).

For example, given 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

Input Format:

• The first line contains an integer n representing the number of elements in the sequence.
• The second line contains n integers separated by spaces.

Note: The input is read from standard input (stdin).

outputFormat

Output Format:

• Print a single integer, the length of the longest increasing subsequence.

The output should be written to standard output (stdout).

## sample

8
10 9 2 5 3 7 101 18

4

</p>