UOJ Logo

NOI.AC

1S 512MB
统计

最长公共子序列

输入两个数字序列,求最长公共子序列的长度。

输入描述

第一行一个$n$

接下来一行$n$个数字,表示第一个数字序列$a_i$。

接下来一行$n$个数字,表示第二个数字序列$b_i$。

输出描述

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

样例输入

6
1 2 3 3 2 1
1 2 3 1 2 3

样例输出

4

数据规模与约定

对于$100$%的数据,$n \le 3e5$,$1 \le a_i$, $b_i \le n$,每个数字在序列$a_i$中最多出现三次。

对于$30$%的数据,$n \le 3e3$

对于另$30$%的数据,每个数字在序列$a_i$中最多出现一次。