5034. 「POI2016 R2」口吃 Stutter

题目译自 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$。

附加样例

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

数据范围与提示