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.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jialin Ouyang (Jialin.Ouyang@gmail.com)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    QuickScanner in = new QuickScanner(inputStream);
    QuickWriter out = new QuickWriter(outputStream);
    TaskD solver = new TaskD();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskD {
    int n;
    int[] a;
    int[] a7;
    int[][] singleJump;
    int[][] jump;
    IntIntToBoolBiFunction INC = (x, y) -> a[x] + 1 == a[y];
    IntIntToBoolBiFunction DEC = (x, y) -> a[x] - 1 == a[y];
    IntIntToBoolBiFunction SAME = (x, y) -> a7[x] == a7[y];
    IntIntToBoolBiFunction[] checkers = new IntIntToBoolBiFunction[]{INC, DEC, SAME};
    int[] singleDP;
    int[][] dp;

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      n = in.nextInt();
      a = in.nextInt(n);
      a7 = new int[n];
      for (int i = 0; i < n; ++i) a7[i] = a[i] % 7;
      singleJump = new int[3][n];
      for (int mode = 0; mode < 3; ++mode) {
        initSingleJump(singleJump[mode], checkers[mode]);
      }
      jump = new int[3][n];
      out.println(calc());
    }

    void initSingleJump(int[] singleJump, IntIntToBoolBiFunction checker) {
      for (int i = 0; i < n; ++i) {
        int res = -1;
        for (int j = i + 1; j < n; ++j) {
          if (checker.apply(i, j)) {
            res = j;
            break;
          }
        }
        singleJump[i] = res;
      }
    }

    void initJump(int startIdx, int mode, int[] jump, IntIntToBoolBiFunction checker) {
      int res = -1;
      for (int i = n - 1; i > startIdx; --i) {
        jump[i] = res;
        if (checker.apply(startIdx, i)) {
          res = i;
        }
      }
      jump[startIdx] = singleJump[mode][startIdx];
    }

    int calc() {
      singleDP = new int[n];
      Arrays.fill(singleDP, 1);
      dp = new int[n][n];
      for (int i = 0; i < n; ++i) {
        Arrays.fill(dp[i], i + 1, n, 2);
      }
      int res = 0;
      for (int i = 0; i < n; ++i) {
        for (int mode = 0; mode < 3; ++mode) {
          initJump(i, mode, jump[mode], checkers[mode]);
        }
        int newValue = singleDP[i] + 1;
        for (int mode = 0; mode < 3; ++mode) {
          if (jump[mode][i] > i) {
            updateSingle(jump[mode][i], newValue);
          }
        }
        newValue = singleDP[i] + 1;
        for (int j = i + 1; j < n; ++j) {
          update(i, j, newValue);
        }
        for (int j = i + 1; j < n; ++j) {
          newValue = dp[i][j] + 1;
          for (int mode = 0; mode < 3; ++mode) {
            if (singleJump[mode][j] > j) {
              update(i, singleJump[mode][j], newValue);
            }
            if (jump[mode][j] > j) {
              update(j, jump[mode][j], newValue);
            }
          }
          res = Math.max(res, dp[i][j]);
        }
      }
      return res;
    }

    void updateSingle(int x, int value) {
      singleDP[x] = Math.max(singleDP[x], value);
    }

    void update(int x, int y, int value) {
      dp[x][y] = Math.max(dp[x][y], value);
    }

  }

  static interface IntIntToBoolBiFunction {
    boolean apply(int x, int y);

  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPosition;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPosition = 0;
      this.numberOfChars = 0;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public int[] nextInt(int n) {
      int[] res = new int[n];
      nextInt(n, res);
      return res;
    }

    public void nextInt(int n, int[] res) {
      for (int i = 0; i < n; ++i) {
        res[i] = nextInt();
      }
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPosition >= numberOfChars) {
        currentPosition = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPosition++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' ' || c == '\t' || isEndOfLineChar(c);
    }

    public boolean isEndOfLineChar(int c) {
      return c == '\n' || c == '\r' || c < 0;
    }

  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public QuickWriter(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.print('\n');
    }

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

  }
}