← 返回题目列表

Codeforces · 818/G

G. 四首旋律

中文机器翻译题面 查看原题

作者注:我想你们中的一些人可能还记得 Educational Codeforces 第 22 轮中的“Two Melodies”问题。现在是时候让它变得更加困难了!

Alice是一位作曲家,最近她录制了两首非常受欢迎的歌曲。现在,她已经拥有了很多粉丝,他们正在等待新曲目。

这次爱丽丝想为她的曲目创作四首旋律。

Alice 有一张纸,上面写着 n 个笔记。她想要取四个这样的非空非相交子序列,使它们全部形成旋律,并且它们的长度之和最大。

子序列是可以通过删除某些元素而不改变剩余元素的顺序从另一个序列导出的序列。

当每两个相邻音符相差 1 或模 7 全等时,子序列形成旋律。

您应该编写一个程序来计算四个非空非相交子序列的最大长度总和,使它们全部形成旋律。

输入

第一行包含一个整数 n (4 ≤ n ≤ 3000)。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 105) — 写在纸上的注释。

输出

打印这四个非空非相交子序列的最大长度总和,使它们全部形成旋律。

示例

输入 #1

5
1 3 5 7 9

输出 #1

4

输入 #2

5
1 3 5 7 2

输出 #2

5

注意

在第一个示例中,可以通过选择任意 4 个音符来创作 4 首旋律(每个旋律仅包含一个音符)。

在第二个示例中,可以用 2 个音符 - {1, 2} 创作一首旋律。其余音符用于其他三个旋律(每个旋律一个音符)。