Longest Common Increasing Subsequence

Problem Background

Special for beginners, ^_^

Problem Description

Mother Bear's cows, influenced by little Mumu, began studying informatics problems.

Mumu first had them study the longest increasing subsequence, then the longest common subsequence, and now the longest common increasing subsequence.

Mumu says: for two sequences A and B, if both contain a segment of numbers whose positions need not be consecutive and whose values are strictly increasing, then that segment is a common increasing subsequence of the two sequences; among all common increasing subsequences, the longest is the longest common increasing subsequence.

The cows half-understand, so Mumu asks you to tell them what the longest common increasing subsequence is. But you only need to tell them its length.

Both sequences A and B have length at most 3000.

Input Format

The first line contains an integer $N$ — the length of sequences A and B.

The second line contains $N$ integers — sequence A.

The third line contains $N$ integers — sequence B.

Output Format

Output one integer — the length of the longest common increasing subsequence.

Sample Input

4
2 2 1 3
2 1 2 3

Sample Output

2

Constraints

$1\le N\le 3000$; all numbers in the sequences are at most $2^{31}-1$.

Time limit 1s, memory limit 1024KiB for each test case.