Longest Increasing Subsequence

Given an array of integers, your task is to compute the length of the longest strictly increasing subsequence (LIS) within the array. A subsequence is derived by deleting some or no elements without changing the order of the remaining elements. The problem can be mathematically expressed as finding the maximum length L such that there exists indices 1 ≤ i₁ < i₂ < ... < i_L with the property:

$$a_{i_1} < a_{i_2} < \cdots < a_{i_L}.$$

Note: The subsequence does not need to be contiguous. For example, for the array [10, 9, 2, 5, 3, 7, 101, 18], the longest increasing subsequence is [2, 3, 7, 101] which has a length of 4.

inputFormat

The input is read from standard input (stdin). The first line contains a non-negative integer n representing the number of elements in the array. The second line contains n space-separated integers.

For example:

8
10 9 2 5 3 7 101 18

outputFormat

Output to standard output (stdout) a single integer: the length of the longest strictly increasing subsequence of the given array.

For the above example, the output should be:

4

## sample

8
10 9 2 5 3 7 101 18

4