Two Melodies

题意翻译

给定一个$n$,以及$n$个数 $a_1,a_2,a_3,\cdots,a_n$,定义一个$Melody$子序列(和"最长上升子序列"中的"子序列"定义一样,是指在原序列中相对顺序不变但是不一定连续的一段子序列)如下: 对于任意相邻的两个元素,一定满足这两个元素差为1或者两个元素除7同余。 请在原序列中找出两个无重复部分的Melody子序列并且选出的两个长度加起来最大。 > 解释:样例2中选出$62,48,49$和$60,61$这两个Melody子序列能使得总长度最大$=5(\text{即2+3})$。

题目描述

Alice is a beginner composer and now she is ready to create another masterpiece. And not even the single one but two at the same time! Alice has a sheet with $ n $ notes written on it. She wants to take two such non-empty non-intersecting subsequences that both of them form a melody and sum of their lengths is maximal. Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. Subsequence forms a melody when each two adjacent notes either differs by 1 or are congruent modulo 7. You should write a program which will calculate maximum sum of lengths of such two non-empty non-intersecting subsequences that both of them form a melody.

输入输出格式

输入格式


The first line contains one integer number $ n $ ( $ 2<=n<=5000 $ ). The second line contains $ n $ integer numbers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{5} $ ) — notes written on a sheet.

输出格式


Print maximum sum of lengths of such two non-empty non-intersecting subsequences that both of them form a melody.

输入输出样例

输入样例 #1

4
1 2 4 5

输出样例 #1

4

输入样例 #2

6
62 22 60 61 48 49

输出样例 #2

5

说明

In the first example subsequences $ [1,2] $ and $ [4,5] $ give length 4 in total. In the second example subsequences $ [62,48,49] $ and $ [60,61] $ give length 5 in total. If you choose subsequence $ [62,61] $ in the first place then the second melody will have maximum length 2, that gives the result of 4, which is not maximal.