Longest Increasing Subsequence

You are given an array of integers. Your task is to determine the length of the longest increasing subsequence (LIS) in the array using dynamic programming.

An increasing subsequence is a sequence where every element is strictly greater than its preceding element. Note that the subsequence is not necessarily contiguous in the original array.

The recurrence relation for the dynamic programming solution is given by:

$$dp[i] = \max_{0 \leq j < i \text{ and } arr[i] > arr[j]} (dp[j] + 1) $$

For an empty array, the answer is defined as 0.

Read the input from standard input and output the result to standard output.

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.

outputFormat

Output a single integer: the length of the longest increasing subsequence.## sample

0

0