Problem: Author note: I think some of you might remember the problem "Two Melodies" from Eductational Codeforces Round 22. Now it's time to make it a bit more difficult!

Alice is a composer, and recently she had recorded two tracks that became very popular. Now she has got a lot of fans who are waiting for new tracks. 

This time Alice wants to form four melodies for her tracks.

Alice has a sheet with n notes written on it. She wants to take four such non-empty non-intersecting subsequences that all 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 differ by 1 or are congruent modulo 7.

You should write a program which will calculate maximum sum of lengths of such four non-empty non-intersecting subsequences that all of them form a melody.

Input

The first line contains one integer number n (4 ≤ n ≤ 3000).

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 105) — notes written on a sheet.

Output

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

Examples

Input

5
1 3 5 7 9


Output

4


Input

5
1 3 5 7 2


Output

5

Note

In the first example it is possible to compose 4 melodies by choosing any 4 notes (and each melody will consist of only one note).

In the second example it is possible to compose one melody with 2 notes — {1, 2}. Remaining notes are used in other three melodies (one note per each melody).

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

/**
 *
 * @author Jishnu_T
 */
public class TwoMelodies {
    
    private static long maxSum(int n, int[] ar)
    {
        int[][] dp = new int[n+1][n+1];
        int[] maxModIndex = new int[7];
        int[] maxNumIndex = new int[100002];
       
        for(int y=0;y<n;y++)
        {
            for(int i=0;i<7;i++)
            {
                maxModIndex[i] = -1;
            }

            for(int i=0;i<100002;i++)
            {
                maxNumIndex[i] = -1;
            }
            for(int x=1;x<=n;x++)
            {
                if(x==1 && y==0)
                {
                    dp[x][y] = 1;
                    dp[y][x] = 1;
                    int mod = ar[x]%7;
                    maxModIndex[mod] = x;
                    maxNumIndex[ar[x]] = x;
                }
                else
                {
                    if(x<y)
                    {
                        int mod = ar[x]%7;
                        if(maxModIndex[mod]==-1 || dp[y][x]>dp[y][maxModIndex[mod]])
                            maxModIndex[mod] = x;
                        if(maxNumIndex[ar[x]]==-1 || dp[y][x]>dp[y][maxNumIndex[ar[x]]])
                            maxNumIndex[ar[x]] = x;
                    }
                    else if(x>y)
                    {
                        int mod = ar[x]%7;
                        dp[x][y] = Integer.MIN_VALUE;
                        if(maxModIndex[mod]!=-1 && dp[maxModIndex[mod]][y]+1>dp[x][y])
                        {
                            dp[x][y] = dp[maxModIndex[mod]][y]+1;
                        }
                        if(maxNumIndex[ar[x]+1]!=-1 && dp[maxNumIndex[ar[x]+1]][y]+1>dp[x][y])
                        {
                            dp[x][y] = dp[maxNumIndex[ar[x]+1]][y]+1;
                        }
                        if(maxNumIndex[ar[x]-1]!=-1 && dp[maxNumIndex[ar[x]-1]][y]+1>dp[x][y])
                        {
                            dp[x][y] = dp[maxNumIndex[ar[x]-1]][y]+1;
                        }
                        if(dp[y][0]+1>dp[x][y])
                        {
                            dp[x][y] =dp[y][0]+1;
                        }
                        
                        dp[y][x] = dp[x][y];
                        
                        if(maxModIndex[mod]==-1 || dp[y][x]>dp[y][maxModIndex[mod]])
                            maxModIndex[mod] = x;
                        if(maxNumIndex[ar[x]]==-1 || dp[y][x]>dp[y][maxNumIndex[ar[x]]])
                            maxNumIndex[ar[x]] = x;
                    }
                }
            }
        }
        
        int res=Integer.MIN_VALUE;
        for(int x=2;x<=n;x++)
        {
            for(int y=1;y<x;y++)
            {
                if(dp[x][y]>res)
                    res = dp[x][y];
            }
        }
        return res;
    }
    
     private static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
    public static void main(String args[])
    {
        FastReader r = new FastReader();
        int n = r.nextInt();
        int[] ar = new int[n+1];
        
        for(int i=1;i<=n;i++)
        {
            ar[i] = r.nextInt();
        }
        System.out.println(maxSum(n,ar));
    }
}