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 N = 6010, M = N * 20, INF = 1e9;
int n, a[N], h[N], tot, e[M], nxt[M], fl[M], co[M], f[N], vis[N], calc, now[N],
    D[N], ans, In[N], Out[N], T;
bool bz[N];
void Add(int x, int y, int f, int c) {
  e[++tot] = y;
  nxt[tot] = h[x];
  fl[tot] = f;
  co[tot] = c;
  h[x] = tot;
}
bool aug(int x) {
  vis[x] = calc;
  if (x == T) return 1;
  for (int i = now[x]; i; i = nxt[i])
    if (fl[i] > 0 && f[x] == co[i ^ 1] + f[e[i]] && vis[e[i]] < calc) {
      if (aug(e[i])) {
        fl[i]--;
        fl[i ^ 1]++;
        now[x] = i;
        return 1;
      }
    }
  return now[x] = 0;
}
int main() {
  scanf("%d", &n);
  T = tot = 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    In[i] = ++T;
    Out[i] = ++T;
  }
  T++;
  Add(0, 1, 4, 0);
  Add(1, 0, 0, 0);
  for (int i = 1; i <= n; i++) {
    Add(1, In[i], 1, 0);
    Add(In[i], 1, 0, 0);
    Add(In[i], Out[i], INF, 0);
    Add(Out[i], In[i], 0, 0);
    Add(In[i], Out[i], 1, -1);
    Add(Out[i], In[i], 0, 1);
    Add(Out[i], T, 1, 0);
    Add(T, Out[i], 0, 0);
    for (int j = i + 1; j <= n; j++)
      if (a[i] == a[j] + 1) {
        Add(Out[i], In[j], INF, 0);
        Add(In[j], Out[i], 0, 0);
        break;
      }
    for (int j = i + 1; j <= n; j++)
      if (a[i] == a[j] - 1) {
        Add(Out[i], In[j], INF, 0);
        Add(In[j], Out[i], 0, 0);
        break;
      }
    for (int j = i + 1; j <= n; j++)
      if (a[i] % 7 == a[j] % 7) {
        Add(Out[i], In[j], INF, 0);
        Add(In[j], Out[i], 0, 0);
        break;
      }
  }
  for (;;) {
    D[tot = 1] = T;
    memset(bz, 0, sizeof(bz));
    for (int i = 0; i < T; i++) f[i] = -INF;
    f[T] = 0;
    for (int i = 0, j, x; i != tot;) {
      i = (i + 1) % N;
      x = D[i];
      bz[x] = 0;
      for (j = h[x]; j; j = nxt[j])
        if (fl[j ^ 1] > 0 && f[x] + co[j] > f[e[j]]) {
          f[e[j]] = f[x] + co[j];
          if (!bz[e[j]]) {
            bz[e[j]] = 1;
            tot = (tot + 1) % N;
            D[tot] = e[j];
          }
        }
    }
    if (f[0] <= 0) break;
    for (memcpy(now, h, sizeof(h));;) {
      calc++;
      if (!aug(0)) break;
      ans += f[0];
    }
  }
  printf("%d\n", ans);
  return 0;
}