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 = 20009, S = N - 2, T = N - 1, O = N - 3, M = 1e5 + 3;
int he[N], cur[N], to[M], ne[M], len[M], co[M], d[N], t = 1, a[N];
queue<int> q;
bool f[N];
void add(int x, int y, int z = 4, int w = 0) {
  ne[++t] = he[x], to[t] = y, len[t] = z, co[t] = w, he[x] = t;
  ne[++t] = he[y], to[t] = x, co[t] = -w, he[y] = t;
}
bool spfa() {
  int i, j, k, l;
  memset(d, -9, N * 4), d[S] = 0, f[S] = 1, q.push(S);
  while (!q.empty()) {
    i = q.front(), q.pop(), f[i] = 0;
    for (j = he[i]; j; j = ne[j])
      if (len[j] && d[k = to[j]] < (l = d[i] + co[j]))
        if (d[k] = l, !f[k]) f[k] = 1, q.push(k);
  }
  return d[T] >= 0;
}
int dfs(int x, int y) {
  if (x == T) return y;
  int &i = cur[x], j, u = 0, w;
  for (f[x] = 1; i; i = ne[i])
    if (len[i] && d[j = to[i]] == d[x] + co[i] && !f[j]) {
      w = dfs(j, min(len[i], y - u)), u += w, len[i] -= w, len[i ^ 1] += w;
      if (u == y) break;
    }
  return f[x] = 0, u;
}
int main() {
  int n, i, j, s = 0;
  scanf("%d", &n), add(S, O);
  for (i = 1; i <= n; ++i) scanf("%d", a + i);
  for (i = 1; i <= n; ++i) {
    add(O, i), add(i, i + n, 1, 1), add(i + n * 2, i), add(i + n * 3, i),
        add(i + n, T);
    for (j = i + 1; j <= n; ++j)
      if (a[j] == a[i] - 1) {
        add(i + n, j + n * 2);
        break;
      }
    for (j = i + 1; j <= n; ++j)
      if (a[j] == a[i] + 1) {
        add(i + n, j + n * 2);
        break;
      }
    for (j = i + 1; j <= n; ++j)
      if (a[j] % 7 == a[i] % 7) {
        add(i + n, j + n * 3), add(i + n * 3, j + n * 3);
        break;
      }
    for (j = i + 1; j <= n; ++j)
      if (a[j] == a[i]) {
        add(i + n * 2, j + n * 2);
        break;
      }
  }
  while (spfa()) memcpy(cur, he, N * 4), s += dfs(S, 1e9) * d[T];
  printf("%d", s);
  return 0;
}