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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TwoMelodies solver = new TwoMelodies();
        solver.solve(1, in, out);
        out.close();
    }

    static class TwoMelodies {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int N = in.nextInt();
            int[] arr = new int[N];
            HashSet<Integer> seen = new HashSet<>();
            for (int i = 0; i < N; i++) {
                int a = in.nextInt();
                arr[i] = a;
                seen.add(a);
            }
            for (int i = 0; i < 7; i++) {
                seen.add(i);
            }
            ArrayList<Integer> mapping = new ArrayList<Integer>(seen);
            DoubleMap map = new DoubleMap();
            for (int i = 0; i < mapping.size(); i++) {
                map.add(mapping.get(i), i);
            }
            int sz = mapping.size();
            int[][] dp = new int[sz][sz];
            int[][] max_first = new int[7][sz];
            int[][] max_second = new int[sz][7];
            for (int i = 0; i < N; i++) {
                int index = map.get(arr[i]);
                int lower = map.get(arr[i] - 1);
                int higher = map.get(arr[i] + 1);
                dp[index][index] = Math.max(dp[index][index], max_second[index][arr[i] % 7] + 1);
                dp[index][index] = Math.max(dp[index][index], max_first[arr[i] % 7][index] + 1);
                if (lower != -1) {
                    dp[index][index] = Math.max(dp[index][index], Math.max(dp[index][lower], dp[lower][index]) + 1);
                }
                if (higher != -1) {
                    dp[index][index] = Math.max(dp[index][index], Math.max(dp[index][higher], dp[higher][index]) + 1);
                }
                max_first[arr[i] % 7][index] = dp[index][index];
                max_second[index][arr[i] % 7] = dp[index][index];
                for (int j = 0; j < sz; j++) {
                    if (j == index) {
                        continue;
                    }
                    if (lower != -1) {
                        dp[index][j] = Math.max(dp[index][j], dp[lower][j] + 1);
                    }
                    if (higher != -1) {
                        dp[index][j] = Math.max(dp[index][j], dp[higher][j] + 1);
                    }
                    dp[index][j] = Math.max(dp[index][j], max_first[arr[i] % 7][j] + 1);
                    max_first[arr[i] % 7][j] = dp[index][j];
                    max_second[index][mapping.get(j) % 7] = Math.max(max_second[index][mapping.get(j) % 7], dp[index][j]);
                }
                for (int j = 0; j < sz; j++) {
                    if (j == index) {
                        continue;
                    }
                    if (lower != -1) {
                        dp[j][index] = Math.max(dp[j][index], dp[j][lower] + 1);
                    }
                    if (higher != -1) {
                        dp[j][index] = Math.max(dp[j][index], dp[j][higher] + 1);
                    }
                    dp[j][index] = Math.max(dp[index][j], max_second[j][arr[i] % 7] + 1);
                    max_second[j][arr[i] % 7] = dp[index][j];
                    max_first[mapping.get(j) % 7][index] = Math.max(max_first[mapping.get(j) % 7][index], dp[index][j]);
                }
            }
            int res = 0;
            for (int i = 0; i < sz; i++) {
                for (int j = 0; j < sz; j++) {
                    res = Math.max(dp[i][j], res);
                }
            }
            out.println(res);
        }

        class DoubleMap {
            HashMap<Integer, Integer> forward = new HashMap<>();

            void add(int a, int b) {
                forward.put(a, b);
            }

            int get(int a) {
                if (!forward.containsKey(a)) {
                    return -1;
                }
                return forward.get(a);
            }

        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}