← 返回题目列表

Codeforces · 813/D

D. 两首旋律

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

Alice 是一名初学者作曲家,现在她准备创作另一部杰作。而且不是单个的,而是同时两个!

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

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

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

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

输入

第一行包含一个整数 n (2 ≤ n ≤ 5000)。

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

输出

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

示例

输入 #1

4
1 2 4 5

输出 #1

4

输入 #2

6
62 22 60 61 48 49

输出 #2

5

注意

在第一个示例中,子序列 [1, 2] 和 [4, 5] 总共给出长度 4。

在第二个示例中,子序列 [62, 48, 49] 和 [60, 61] 总共给出长度 5。如果您首先选择子序列 [62, 61],那么第二个旋律的最大长度将为 2,这给出的结果为 4,这不是最大的。