721. Longest Increasing subsequence

0

Medium

Determine the length of the longest subsequence in a given array A of integers, where all elements of the subsequence are arranged in strictly ascending order.

Input Format

The first line contains a single integer n.

The next line contains n space-separated numbers representing the elements of the array.

The next line contains n space-separated numbers representing the elements of the array.

Output Format

Print a single line containing a single integer representing the length of the longest increasing subsequence.

Example

Input

6
50 3 10 7 40 80

Output

4

Constraints

0 < n < 10^5

0 < A_i < 10^5

0 < A_i < 10^5

Loading...

View Submissions

Console