Longest Increasing Subsequence

In this problem, you are given a sequence of integers and your task is to determine the length of its longest increasing subsequence (LIS). An increasing subsequence is a sequence that can be derived from the original sequence by removing some or no elements without changing the order, and where each subsequent element is strictly greater than its previous element. Formally, if we denote the sequence as (a_1, a_2, \dots, a_n), then the longest increasing subsequence ending at index (i) can be described by the recurrence

[ LIS(i) = \max_{1 \leq j < i \text{ and } a_j < a_i} (LIS(j)) + 1 ]

If the sequence is empty, the output should be 0. Solve the problem using efficient dynamic programming techniques.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (n) which represents the number of elements in the sequence. The second line contains (n) space-separated integers representing the sequence.

outputFormat

Output to standard output (stdout) a single integer which is the length of the longest increasing subsequence in the given sequence.## sample

8
5 1 6 2 7 1 8 3

4