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.InputStreamReader;
import java.io.PrintWriter;

// author: olya-chuchuk

public class Ds{
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(in.readLine());
		
		String[] line = in.readLine().split("\\s+");
		
		int[] arr = new int[n+1];
		
		for(int i=1; i<=n; i++) {
			arr[i] = Integer.parseInt(line[i-1]);
		}
		
		int[][] dp = new int[n+1][n+1];
		
		int ans = 0;
		
		for(int back=0; back<=n; back++) {
			
			if(back == 2) {
				System.out.println();
			}
			
			int[] mod7 = new int[7];
			int[] maxVal = new int[100005];
			
			for(int front=0; front<=n; front++) {
				
				if(front == back) {
					continue;
				}
				else if(back > front) {
					dp[front][back] = dp[back][front];
				}
				else {
					
					// start new sequence
					dp[front][back] = 1 + dp[0][back];
					
					dp[front][back] = Math.max(dp[front][back], 1 + mod7[arr[front] % 7]);
					
					dp[front][back] = Math.max(dp[front][back], 1 + maxVal[arr[front]+1]);
					
					if(arr[front] >= 1) {
						dp[front][back] = Math.max(dp[front][back], 1 + maxVal[arr[front]-1]);
					}

				}
				
				mod7[arr[front] % 7] = Math.max(mod7[arr[front] % 7], dp[front][back]);
				maxVal[arr[front]] = Math.max(maxVal[arr[front]], dp[front][back]);
				
				ans = Math.max(ans, dp[front][back]);
			}
		}
		
		
		System.out.println(ans);
		
	}
	
}