Longest Increasing Subsequence

You are given an array of integers. Your task is to compute the length of the longest increasing subsequence (LIS) in the array. A 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.

The classic dynamic programming solution uses an array dp where dp[i] represents the length of the longest increasing subsequence ending at index i. The recurrence is given by:

$$dp[i] = \max_{0 \leq j nums[j]}\{dp[j]\} + 1$$

If the array is empty, the answer is 0.

inputFormat

The first line of input contains an integer n representing the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

outputFormat

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

## sample

8
10 9 2 5 3 7 101 18

4

</p>