[USACO5.1] 乐曲主题Musical Themes

题目描述

我们用 $N$($1 \le N \le 5000$)个音符的序列来表示一首乐曲,每个音符都是 $1 \sim 88$ 范围内的整数,每个数表示钢琴上的一个键。很不幸这种表示旋律的方法忽略了音符的时值,但这项编程任务是关于音高的,与时值无关。 许多作曲家围绕一个重复出现的“主题”来构建乐曲。在我们的乐曲表示法中,“主题”是整个音符序列的一个子串,它需要满足如下条件: 1. 长度至少为 $5$ 个音符。 2. 在乐曲中重复出现(可能经过转调,见下)。 3. 重复出现的同一主题不能有公共部分。 “转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值。给定一段乐曲,计算其中最长主题的长度(即音符数)。 本题时限为 $1$ 秒钟!

输入输出格式

输入格式


输入文件的第一行包含整数 $N$。 下面的每一行(最后一行可能除外)包含 $20$ 个整数,表示音符序列。 最后一行可能少于 $20$ 个音符。

输出格式


输出文件应只含一个整数,即最长主题的长度。如果乐曲中没有主题,那么输出 `0`。

输入输出样例

输入样例 #1

30
25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18
82 78 74 70 66 67 64 60 65 80

输出样例 #1

5

说明

题目翻译来自NOCOW。 USACO Training Section 5.1