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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Abood2C {

	static int N;
	static int[][] nxt;

	static int[][] memo;

	static int solve(int i, int j) {

		if(i > j)
			return solve(j, i);
		
		if(i == N && j == N)
			return 0;

		if(memo[i][j] != -1)
			return memo[i][j];
		int ans = 0;

		for (int k = 0; k < 8; ++k) {
			int a = nxt[k][i];
			
			if(a == j)
				continue;

			ans = Math.max(ans, solve(a, j));
		}	
		
//		ans = Math.max(ans, solve(N, j));
		
		ans++;

		return memo[i][j] = ans;
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		N = sc.nextInt();
		nxt = new int[9][N + 1];

		for (int i = 0; i < 9; ++i)
			Arrays.fill(nxt[i], N);

		int[] O = new int[(int) 1e5 + 5];
		int[] C = new int[7];
		int[] lastSE = new int[(int) 1e5 + 5];
		int[] lastE = new int[(int) 1e5 + 5];

		Arrays.fill(O, N);
		Arrays.fill(C, N);
		Arrays.fill(lastE, N);
		Arrays.fill(lastSE, N);

		int[] arr = new int[N];

		for (int i = 0; i < N; ++i)
			arr[i] = sc.nextInt();

		for (int i = N - 1; i >= 0; --i) {
			nxt[0][i] = C[arr[i] % 7];
			nxt[1][i] = nxt[0][nxt[0][i]];
			nxt[2][i] = nxt[1][nxt[0][i]];
			C[arr[i] % 7] = i;
			
			lastSE[arr[i]] = lastE[arr[i]];
			lastE[arr[i]] = O[arr[i]];
			O[arr[i]] = i;

			nxt[3][i] = O[arr[i] + 1];
			nxt[4][i] = lastE[arr[i] + 1];
			nxt[5][i] = lastSE[arr[i] + 1];

			nxt[6][i] = O[arr[i] - 1];
			nxt[7][i] = lastE[arr[i] - 1];
			nxt[8][i] = lastSE[arr[i] - 1];

		}
		


		memo = new int[N + 1][N + 1];

		for (int i = 0; i <= N; i++)
			Arrays.fill(memo[i], -1);

		int ans = 0;

		for (int i = 0; i < N; ++i) 
			for (int j = i + 1; j < N; ++j) 
					ans = Math.max(ans, solve(i, j));

		out.println(ans);
		out.flush();
		out.close();
	}



	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream System){br = new BufferedReader(new InputStreamReader(System));}
		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public String nextLine()throws IOException{return br.readLine();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		public char nextChar()throws IOException{return next().charAt(0);}
		public Long nextLong()throws IOException{return Long.parseLong(next());}
		public boolean ready() throws IOException{return br.ready();}
		public void waitForInput(){for(long i = 0; i < 3e9; i++);}
	}


}