Longest Increasing Subsequence

In this problem, you are given a sequence of integers and your task is to find the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. Formally, given a sequence (a_1, a_2, \ldots, a_n), you need to find the maximum integer (k) such that there exists an increasing subsequence (a_{i_1}, a_{i_2}, \ldots, a_{i_k}) with (i_1 < i_2 < \ldots < i_k) and (a_{i_1} < a_{i_2} < \ldots < a_{i_k}).

inputFormat

The input is given via standard input. The first line contains a single integer (n) representing the number of elements in the sequence. The second line contains (n) space-separated integers representing the sequence. Note that (n) can be zero.

outputFormat

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

0

0