Longest Increasing Subsequence

You are given a sequence of integers. Your task is to compute the length of the longest strictly increasing subsequence (LIS) of the given sequence. A subsequence is derived from the original sequence by deleting some or no elements without changing the order of the remaining elements.

For example, given the sequence [1, 3, 5, 4, 7], the longest strictly increasing subsequence is [1, 3, 4, 7] with length 4.

The problem can be mathematically interpreted as finding the maximum $k$ such that there exists indices $i_1 < i_2 < \cdots < i_k$ satisfying [ a_{i_1} < a_{i_2} < \cdots < a_{i_k}, ] where $a_{i}$ are the elements of the input sequence.

inputFormat

The input is read from standard input (stdin). The first line contains an integer $N$ representing the number of elements in the sequence. If $N > 0$, the second line contains $N$ space-separated integers. If $N = 0$, no second line is provided.

outputFormat

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

5
1 3 5 4 7

4