Longest Increasing Subsequence

You are given a sequence of n integers. Your task is to find the length of the longest strictly increasing subsequence in the sequence.

A subsequence is a sequence that can be derived from the original sequence by deleting some or no elements without changing the order of the remaining elements.

The dynamic programming solution can be derived using the recurrence relation:

\( dp[i] = \max_{\substack{0 \leq j < i \\ a_j < a_i}}(dp[j]) + 1 \)

If the sequence is empty, the result should be 0.

inputFormat

The first line of input contains a single integer n (0 \(\leq n \leq 10^5\)), the number of elements in the sequence.

The second line contains n space-separated integers representing the sequence.

If n is 0, the second line may be omitted.

outputFormat

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

## sample

8
10 9 2 5 3 7 101 18

4

</p>