Longest Increasing Subsequence

Given a sequence of ( n ) integers, your task is to determine the length of the longest increasing subsequence (LIS). An increasing subsequence is a sequence where every element is greater than the preceding one. For example, for the array [10, 9, 2, 5, 3, 7, 101, 18], the LIS is [2, 3, 7, 101] and its length is 4. The recurrence relation used in many dynamic programming solutions is given by: ( dp[i] = \max_{0 \leq j < i \text{ and } a_j < a_i} (dp[j]) + 1 ). You are required to implement a solution that reads input from standard input (stdin) and writes the result to standard output (stdout).

inputFormat

The input is given in two lines. The first line contains a single integer ( n ) representing the number of elements in the array. The second line contains ( n ) space-separated integers. If ( n = 0 ), the second line will be omitted.

outputFormat

Output a single integer which is the length of the longest increasing subsequence of the given input sequence.## sample

0

0