You are given an array of ~N~ integers. Find the length of the Longest Increasing Subsequence (LIS).

A subsequence is obtained by deleting zero or more elements without changing the order of the remaining elements. A subsequence is increasing if every next element is strictly larger than the previous one.

Input Format

The first line contains a single integer ~N~.

The second line contains ~N~ integers ~a_1, a_2, ..., a_N~.

Output Format

Print a single integer: the length of the longest increasing subsequence.

Example

Input

8
7 3 5 3 6 2 9 8

Output

4

Explanation

One valid LIS is ~3, 5, 6, 9~, so the answer is ~4~.

Constraints

• ~1 ≤ N ≤ 200000~
• ~1 ≤ a_i ≤ 10^9~

Subtasks

• 80% of the tests satisfy ~N ≤ 2000~. An ~O(N^2)~ solution is accepted here.
• 20% of the tests use the full constraints and require an ~O(N log N)~ solution.