Longest Increasing Subsequence

You are given a sequence of n integers. Your task is to compute the length of the longest strictly increasing subsequence of the given 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. Formally, given a sequence \(a_1, a_2, \dots, a_n\), a subsequence is a sequence \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\) where \(1 \le i_1 < i_2 < \dots < i_k \le n\). The subsequence is strictly increasing if \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\).

Your solution should read from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The input is given from standard input and consists of two lines:

1. The first line contains a single integer n (0 \(\leq n \leq 10^5\)) representing the number of elements in the sequence.
2. The second line contains n space-separated integers representing the sequence.

outputFormat

Output a single integer, which is the length of the longest strictly increasing subsequence.

## sample

6
5 8 3 7 9 1

3

</p>