[AdditionalFile5034.zip](file://AdditionalFile5034.zip?type=additional_file)

#5034. 「POI2016 R2」口吃 Stutter

标签: 传统 | 时间限制: 10000 ms | 内存限制: 32 MiB |

题目描述

题目译自 XXIII Olimpiada Informatyczna — II etap Zająknięcia

Bitek 最近患上了一种怪病：他说话严重口吃，而且只会说出数字。他的哥哥 Bajtek 却发现，Bitek 的口吃模式似乎有规律可循。Bajtek 怀疑弟弟在装病，借此逃学，偷偷在家玩电脑游戏。这让 Bajtek 无法专心学习编程，感到十分沮丧。于是，他决定揭穿弟弟的把戏，希望借此赢得充足的编程时间。

让我们来正式描述 Bajtek 的猜想。假设有两个数字序列 $A$ 和 $B$，分别表示 Bitek 的两次发言：

• 序列 $A$ 的子序列是通过从 $A$ 中删除任意元素后得到的序列。例如，$1,1,7,5$ 是 $1,3,1,7,6,6,5,5$ 的子序列。
• 序列 $A$ 的“口吃序列”是一个子序列，由连续的成对相同元素组成。例如，$1,1,1,1,3,3$ 是 $1,2,1,2,1,2,1,3,3$ 的口吃序列。

给定 Bitek 的两次发言序列 $A$ 和 $B$，请帮助 Bajtek 找出同时出现在两个序列中的最长口吃序列的长度。

输入格式

第一行包含两个整数 $n, m$ $(n, m \geq 2)$，分别表示序列 $A$ 和 $B$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^9)$，表示序列 $A$ 的元素。

第三行包含 $m$ 个整数 $b_1, b_2, \ldots, b_m$ $(1 \leq b_i \leq 10^9)$，表示序列 $B$ 的元素。

输出格式

输出一个非负整数，表示序列 $A$ 和 $B$ 的最长公共口吃序列的长度。若无公共口吃序列，输出 $0$。

样例

输入

7 9
1 2 2 3 1 1 1
2 4 2 3 1 2 4 1 1

输出

4

最长公共口吃序列为 $2, 2, 1, 1$。

附加样例

1. $n=5, m=4$，所有数字均为 $42$。
2. $n=9, m=13$，序列为 OLIMPIADA 和 INFORMATYCZNA 的 ASCII 编码。
3. $n=15000, m=15000$，序列 $A$ 由成对递增数字组成（$1,1,2,2,3,3,\ldots,7500,7500$），序列 $B$ 为 $A$ 的逆序。
4. $n=10000, m=5000$，两序列由 $13$ 和 $37$ 的成对交替组成（$13,37,13,37,\ldots$）。

数据范围与提示

详细子任务附加限制及分值如下表所示。