Longest Increasing Subsequence

You are given a sequence of integers. Your task is to find the length of the Longest Increasing Subsequence (LIS) in the sequence. An increasing subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements, and every element in the subsequence is strictly greater than its previous element.

For example, given the sequence:

$$[10,\ 9,\ 2,\ 5,\ 3,\ 7,\ 101,\ 18]$$

the longest increasing subsequence is [2, 3, 7, 101], and its length is 4.

You need to read the input from stdin and output the result to stdout.

inputFormat

The first line of input contains a single integer n (0 ≤ n ≤ 10⁵), representing the number of elements in the sequence. If n is greater than 0, the second line contains n space-separated integers representing the sequence.

outputFormat

Output a single integer - the length of the longest increasing subsequence of the given sequence.

## sample

8
10 9 2 5 3 7 101 18

4