Longest Increasing Subsequence

You are given a sequence of integers, and your task is to compute the length of the Longest Increasing Subsequence (LIS) of the sequence. An increasing subsequence is a sequence in which each element is strictly greater than its previous element. Formally, if the subsequence is \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\) (with \(i_1 < i_2 < \ldots < i_k\)), then it satisfies \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\). Your solution should read the input from stdin and output the result to stdout.

Example:

Input:
5
3 10 2 1 20
Output:
3

</p>

In the above example, one of the longest increasing subsequences is [3, 10, 20] and its length is 3.

inputFormat

The input consists of two lines. The first line contains a single integer \(n\) representing the number of elements in the sequence. The second line contains \(n\) space-separated integers which form the sequence.

\(1 \leq n \leq 10^5\) (you may assume reasonable constraints for the problem).

outputFormat

Output a single integer which is the length of the longest increasing subsequence in the given sequence.

## sample

5
3 10 2 1 20

3