Problem Description

Aunt Xiong’s cows, influenced by Xiao Mumu, have started studying informatics problems. Xiao Mumu first had the cows study the Longest Increasing Subsequence, then the Longest Common Subsequence, and now he wants them to study the Longest Common Increasing Subsequence.

Xiao Mumu says: for two sequences $A$ and $B$, if they both contain a sequence of numbers that is not necessarily contiguous in position, and the numbers are strictly increasing, then this sequence of numbers is a common increasing subsequence of the two sequences. Among all common increasing subsequences, the longest one is the Longest Common Increasing Subsequence.

The cows do not fully understand, so Xiao Mumu wants you to explain to them what the Longest Common Increasing Subsequence is. However, you only need to tell the cows its length.

Input Format

The first line contains $N$, the length of $A$ and $B$.

The second line contains sequence $A$.

The third line contains sequence $B$.

Output Format

Output the length of the Longest Common Increasing Subsequence.

4
2 2 1 3
2 1 2 3

2

Hint

$1\le N \le 3000$，$0\leq |A_i|,|B_i| \leq 10^6$。

Translated by ChatGPT 5