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;
inline int read() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) f = c == '-' ? 1 : 0;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  return f ? -x : x;
}
const int N = 6005, M = 2000005, oo = 0x3f3f3f3f;
int n, A[N], S, S2, T, ll = 1, to[M], nxt[M], fl[M], co[M], hd[N], ds[N], pr[N],
                       qu[N], ans, pos[100005], pm[7];
bool inq[N];
inline void adde(int u, int v, int w, int c) {
  to[++ll] = v, nxt[ll] = hd[u], hd[u] = ll, fl[ll] = w, co[ll] = c;
  to[++ll] = u, nxt[ll] = hd[v], hd[v] = ll, fl[ll] = 0, co[ll] = -c;
}
inline bool spfa() {
  memset(ds + 1, -1, sizeof(int) * T);
  memset(inq + 1, 0, sizeof(bool) * T);
  int l = 0, r = 1;
  ds[S] = 0, qu[0] = S, inq[S] = 1;
  while (l != r) {
    int u = qu[l++];
    if (l == N) l = 0;
    inq[u] = 0;
    for (int i = hd[u], v; i; i = nxt[i])
      if (fl[i] && ds[v = to[i]] < ds[u] + co[i]) {
        ds[v] = ds[u] + co[i], pr[v] = i;
        if (!inq[v]) {
          qu[r++] = v, inq[v] = 1;
          if (r == N) r = 0;
        }
      }
  }
  return ~ds[T];
}
int main() {
  n = read(), S = 2 * n + 1, S2 = S + 1, T = S + 2;
  for (int i = 1; i <= n; i++) A[i] = read();
  adde(S, S2, 4, 0);
  for (int i = 1; i <= n; i++)
    adde(S2, i, 1, 0), adde(n + i, T, 1, 0), adde(i, n + i, 1, 1),
        adde(i, i + n, 4, 0);
  for (int i = 1, a, r; i <= n; i++) {
    if (a = pos[A[i] - 1]) adde(a + n, i, 4, 0);
    if (a = pos[A[i] + 1]) adde(a + n, i, 4, 0);
    if (a = pm[r = A[i] % 7]) adde(a + n, i, 4, 0);
    pos[A[i]] = i, pm[r] = i;
  }
  while (spfa()) {
    int f = oo;
    for (int i = pr[T]; i; i = pr[to[i ^ 1]]) f = min(f, fl[i]);
    for (int i = pr[T]; i; i = pr[to[i ^ 1]])
      fl[i] -= f, fl[i ^ 1] += f, ans += f * co[i];
  }
  printf("%d\n", ans);
  return 0;
}