Longest Increasing Subsequence

You are given a sequence of n integers. Your task is to compute the length of the longest increasing subsequence (LIS) in the sequence. An increasing subsequence is a subset of the array such that the elements are strictly increasing, and they are taken in the same order as they appear in the original sequence.

The problem can be formally defined as follows:

Given an array \( a_1, a_2, \dots, a_n \), find the maximum integer \( k \) for which there exists indices \( 1 \le i_1 < i_2 < \cdots < i_k \le n \) such that \( a_{i_1} < a_{i_2} < \cdots < a_{i_k} \).

Note: The subsequence is not required to be contiguous.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer n (the number of elements in the sequence).
• The second line contains n space-separated integers representing the sequence.

outputFormat

Output a single integer to stdout: the length of the longest increasing subsequence.

## sample

8
10 9 2 5 3 7 101 18

4

</p>