Longest Increasing Subsequence

Given an array of integers, your task is to compute the length of the longest strictly increasing subsequence (LIS) in the array. A subsequence is obtained by deleting some (or no) elements without changing the order of the remaining elements. The increasing subsequence should satisfy

[ a_{i_1} < a_{i_2} < \cdots < a_{i_k} ]

where (a_{i_j}) are the elements of the subsequence. For example, given the array [10, 9, 2, 5, 3, 7, 101, 18], the length of the longest increasing subsequence is 4 (one possible subsequence is [2, 3, 7, 101]).

inputFormat

The first line of input contains an integer (n) ((0 \leq n \leq 10^5)) representing the number of elements in the array. The second line contains (n) space-separated integers representing the elements of the array. If (n = 0), the second line may be omitted.

outputFormat

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

8
10 9 2 5 3 7 101 18

4