Longest Increasing Subsequence

Given a sequence of integers, find the length of the longest strictly increasing subsequence (LIS). Formally, given an array \(a_1, a_2, \dots, a_n\), a subsequence \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\) is called strictly increasing if \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\). Your task is to compute the maximum possible value of \(k\) for the given array.

Example:

Input:
6
5 2 8 6 3 6
Output:
3

</p>

In the sample above, one possible longest increasing subsequence is [2, 3, 6], so the result is 3.

inputFormat

The input is provided via standard input (stdin) in the following format:

• The first line contains an integer \(n\) representing the number of elements in the sequence.
• The second line contains \(n\) space-separated integers.

If \(n = 0\), then the sequence is empty.

outputFormat

Output a single integer via standard output (stdout): the length of the longest strictly increasing subsequence.

## sample

0

0