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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MN = 5010;
int N;
int A[MN], chk[100010];
int Xn;
vector<int> X;
map<int, int> dx;
int mx1[MN][MN], mx2[MN][7];
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%d", &A[i]);
    X.push_back(A[i]);
    chk[A[i]] = 1;
  }
  sort(X.begin(), X.end());
  X.resize(unique(X.begin(), X.end()) - X.begin());
  Xn = X.size();
  for (int i = 0; i < Xn; i++) dx[X[i]] = i;
  for (int i = 1; i <= N; i++) A[i] = dx[A[i]];
  int ans = 0;
  for (int i = N; i >= 0; i--) {
    for (int j = N; j > i; j--) {
      int t = 0;
      if (chk[X[A[j]] + 1]) t = max(t, mx1[i][A[j] + 1]);
      if (X[A[j]] && chk[X[A[j]] - 1]) t = max(t, mx1[i][A[j] - 1]);
      t = max(t, mx2[i][X[A[j]] % 7]);
      if (i) {
        if (chk[X[A[i]] + 1]) t = max(t, mx1[j][A[i] + 1]);
        if (X[A[i]] && chk[X[A[i]] - 1]) t = max(t, mx1[j][A[i] - 1]);
        t = max(t, mx2[j][X[A[i]] % 7]);
      } else {
        for (int k = 0; k < MN; k++) t = max(t, mx1[j][k]);
        for (int k = 0; k < 7; k++) t = max(t, mx2[j][k]);
      }
      t++;
      mx1[i][A[j]] = max(mx1[i][A[j]], t);
      mx2[i][X[A[j]] % 7] = max(mx2[i][X[A[j]] % 7], t);
      ans = max(ans, t);
    }
  }
  printf("%d", ans);
}