#3260. 最长公共子序列

最长公共子序列

Background

2021年上海交通大学考研机试题

Description

给出两个长度为 n的整数序列,求它们的最长公共子序列(LCS)的长度,保证第一个序列中所有元素都不重复。

注意:

1.第一个序列中的所有元素均不重复。

2.第二个序列中可能有重复元素。

3.一个序列中的某些元素可能不在另一个序列中出现。

Format

Input

第一行包含一个整数 n。

接下来两行,每行包含 n个整数,表示一个整数序列。

Output

输出一个整数,表示最长公共子序列的长度。

Samples

5
1 2 3 4 5
1 2 3 4 5
5
5
1 2 3 5 4
1 2 3 4 5
4

Limitation

1≤n≤10^6, 序列内元素取值范围 [1,10^6]。