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.*;

public class D22 {
    static int n;
    static int a[];
    static int dp[][];
    //if 0 - not used yet, as if used - must be at least 1 (started some sequence)
    static int modMax[] = new int[7];
    static int valMax[];
    static int maxA;
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        OutputWriter out = new OutputWriter(System.out);
        n = in.nextInt();
        a = new int[n + 1];
        dp = new int[n + 1][n + 1];
        maxA = 0;
        for(int i = 1; i <= n; ++i) {
            a[i] = in.nextInt();
            maxA = Integer.max(maxA, a[i]);
        }
        valMax = new int[maxA + 1];
        int ans = 0;
        for(int j = 0; j <= n; ++j) {
            Arrays.fill(modMax, 0);
            Arrays.fill(valMax, 0);
            int curMax = 0;
            for(int i = 0; i <= n; ++i) {
                if(i == j) {
                    continue;
                }
                if(i < j) {
                    dp[i][j] = dp[j][i];
                } else {
                    dp[i][j] = Integer.max(dp[i][j], modMax[a[i] % 7] + 1);
                    if(a[i] > 1) {
                        dp[i][j] = Integer.max(dp[i][j], valMax[a[i] - 1] + 1);
                    }
                    if(a[i] < maxA) {
                        dp[i][j] = Integer.max(dp[i][j], valMax[a[i] + 1] + 1);
                    }
                    dp[i][j] = Integer.max(dp[i][j], dp[j][0] + 1);
                    ans = Integer.max(ans, dp[i][j]);
                }
                modMax[a[i] % 7] = Integer.max(modMax[a[i] % 7], dp[i][j]);
                valMax[a[i]] = Integer.max(valMax[a[i]], dp[i][j]);
            }
        }
//        for(int i = 0; i <= n; ++i) {
//            System.out.println(Arrays.toString(dp[i]));
//        }
        System.out.println(ans);
    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println(Object... objects) {
            print(objects);
            writer.println();
        }

        public void printf(String format, Object... objects) {
            writer.printf(format, objects);
        }

        public void close() {
            writer.close();
        }

        public void flush() {
            writer.flush();
        }

    }
    
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }
}