Longest Increasing Subsequence

You are given a sequence of integers representing transaction amounts. Your task is to determine the length of the longest increasing subsequence (LIS) in the sequence. An increasing subsequence is a sequence of numbers where every subsequent number is strictly greater than the previous one.

For example, given the sequence: [1, 3, 2, 4, 3, 5], one of the longest increasing subsequences is [1, 2, 3, 5] which has a length of 4.

The input is provided via standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

The first line of input contains an integer n (n ≥ 0) indicating the number of transactions. The second line contains n space-separated integers representing the transaction amounts. If n is 0, there will be no second line.

outputFormat

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

1
10

1