Longest Increasing Subsequence

Source of the problem: LeetCode

Given an unsorted array of integers, find the length of longest increasing subsequence (LIS).

For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Input

Each test case contains two lines. The first line consists of only one number n (n ≤ 65535). The second line consists of an unsorted array of n integers, separated by blank spaces.

Output

For each test case, print the length of longest increasing subsequence.

8
10 9 2 5 3 7 101 18

4