题目背景

在整理两份历史档案时，工作人员把同一批文物的编号分别抄录成了两张清单。由于抄录顺序可能不同，他们想知道：两张清单中，按相同先后顺序出现的编号最多有多少个？

这正是经典的"最长公共子序列"问题。

题目描述

给定两个整数序列 $A$（长度为 $n$）和 $B$（长度为 $m$）。

一个序列 $S$ 同时是 $A$ 和 $B$ 的子序列，是指：$S$ 可以由 $A$（同理也可以由 $B$）在不改变剩余元素相对顺序的前提下，删除若干个（可以是 $0$ 个或全部）元素得到。子序列中的元素不要求连续。

请求出两个序列的最长公共子序列（Longest Common Subsequence，LCS）的长度。

序列中的元素允许重复。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示序列 $A$。

第三行一个整数 $m$。

第四行 $m$ 个整数 $b_1,b_2,\dots,b_m$，表示序列 $B$。

输出格式

一行一个整数，表示最长公共子序列的长度。

样例

样例 1 输入

5
1 3 2 5 4
4
3 1 2 4

样例 1 输出

3

样例 1 解释

例如取公共子序列 3 2 4（在 $A$ 中的位置依次是第 2、3、5 个，在 $B$ 中是第 1、3、4 个），长度为 3。不存在长度为 4 的公共子序列。

样例 2 输入

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

样例 2 输出

4

样例 2 解释

元素存在大量重复，需要小心处理相等元素的转移。例如 2 1 2 1 或 2 3 2 3 等都可以构成长度为 4 的公共子序列。

样例 3 输入（稍大规模）

16
7 2 4 6 1 9 2 4 8 3 6 1 5 9 2 4
14
2 4 6 1 3 9 2 4 1 6 8 5 2 4

样例 3 输出

11

样例 3 解释

两条序列都包含多次重复的 2 4 等元素，必须正确处理“相等才能斜向转移”。答案为 11，具体取法不唯一，请自行构造并核对所选元素在两条序列中的位置均严格递增。

数据范围与约定

• $1 \le n, m \le 5000$
• $1 \le a_i, b_i \le 10^9$
• 序列元素允许重复

时间限制：1.0 秒，空间限制：256 MB。

提示

• 设 $f(i,j)$ 表示 $A$ 的前 $i$ 个元素与 $B$ 的前 $j$ 个元素的最长公共子序列长度：
  • 若 $a_i = b_j$，则 $f(i,j)=f(i-1,j-1)+1$；
  • 否则 $f(i,j)=\max(f(i-1,j),f(i,j-1))$。
• 直接开 $5000\times 5000$ 的二维数组会占用较多内存。注意到第 $i$ 行只依赖第 $i-1$ 行，可以用滚动数组把空间压缩到 $O(\min(n,m))$。