Longest Increasing Subsequence

In this problem, you are given a sequence of integers. Your task is to determine the length of the longest strictly increasing subsequence. A subsequence is a sequence derived from the original sequence by deleting some or no elements without changing the order of the remaining elements.

For example, given the sequence: ( [4, 2, 3, 6, 10, 1, 12] ), one of the longest increasing subsequences is ( [2, 3, 6, 10, 12] ) with a length of 5.

inputFormat

The input is given via standard input. The first line contains an integer ( n ) representing the number of elements in the sequence. The second line contains ( n ) space-separated integers.

outputFormat

Output a single integer to standard output, which is the length of the longest strictly increasing subsequence.## sample

7
4 2 3 6 10 1 12

5