Longest Increasing Subsequence

Given a sequence of integers, your task is to find the length of the longest strictly increasing subsequence (LIS) in the sequence. A subsequence is a sequence that can be derived from the original sequence by deleting some or no elements without changing the order of the remaining elements. The strictly increasing subsequence means that each element in the subsequence is greater than its previous element.

The solution should use an efficient dynamic programming approach to solve the problem.

Note: The input will be provided through standard input, and the result should be printed to standard output.

inputFormat

The first line contains a single integer n representing the number of elements in the sequence. The second line contains n space-separated integers representing the sequence. If n is 0, the sequence is empty.

outputFormat

Output a single integer denoting the length of the longest strictly increasing subsequence.

6
5 2 8 6 3 6

3