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>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e4 + 10;
const int M = 1e5 + 10;
bool vis[N];
int dist[N];
int s, t, ans = 0;
int nedge = -1, p[M], c[M], cc[M], nex[M], head[N];
inline void add(int x, int y, int z, int zz) {
  p[++nedge] = y;
  c[nedge] = z;
  cc[nedge] = zz;
  nex[nedge] = head[x];
  head[x] = nedge;
}
void addedge(int x, int y, int z, int zz) {
  add(x, y, z, zz);
  add(y, x, 0, -zz);
}
inline bool spfa(int s, int t) {
  memset(vis, 0, sizeof vis);
  for (int i = 0; i < N; i++) dist[i] = 1e9;
  dist[t] = 0;
  vis[t] = 1;
  deque<int> q;
  q.push_back(t);
  while (!q.empty()) {
    int now = q.front();
    q.pop_front();
    for (int k = head[now]; k > -1; k = nex[k])
      if (c[k ^ 1] && dist[p[k]] > dist[now] - cc[k]) {
        dist[p[k]] = dist[now] - cc[k];
        if (!vis[p[k]]) {
          vis[p[k]] = 1;
          if (!q.empty() && dist[p[k]] < dist[q.front()])
            q.push_front(p[k]);
          else
            q.push_back(p[k]);
        }
      }
    vis[now] = 0;
  }
  return dist[s] < 1e9;
}
inline int dfs(int x, int low) {
  if (x == t) {
    vis[t] = 1;
    return low;
  }
  int used = 0, a;
  vis[x] = 1;
  for (int k = head[x]; k > -1; k = nex[k])
    if (!vis[p[k]] && c[k] && dist[x] - cc[k] == dist[p[k]]) {
      a = dfs(p[k], min(c[k], low - used));
      if (a) ans += a * cc[k], c[k] -= a, c[k ^ 1] += a, used += a;
      if (used == low) break;
    }
  return used;
}
inline int costflow() {
  int flow = 0;
  while (spfa(s, t)) {
    vis[t] = 1;
    while (vis[t]) {
      memset(vis, 0, sizeof vis);
      flow += dfs(s, 1e9);
    }
  }
  return flow;
}
void init() {
  memset(nex, -1, sizeof nex);
  memset(head, -1, sizeof head);
}
int a[N];
int main() {
  std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  init();
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  init();
  s = 0;
  int st = 2 * n + 1;
  t = 2 * n + 2;
  addedge(s, st, 4, 0);
  for (int i = 1; i <= n; i++) {
    addedge(st, i, 1, 0), addedge(n + i, t, 1, 0);
    addedge(i, i + n, 1, -1), addedge(i, n + i, inf, 0);
  }
  for (int i = 2; i <= n; i++) {
    for (int j = i - 1; j; j--) {
      if (a[j] % 7 == a[i] % 7) {
        addedge(n + j, i, 1, 0);
        break;
      }
    }
    for (int j = i - 1; j; j--) {
      if (a[j] == a[i] + 1) {
        addedge(n + j, i, 1, 0);
        break;
      }
    }
    for (int j = i - 1; j; j--) {
      if (a[j] == a[i] - 1) {
        addedge(n + j, i, 1, 0);
        break;
      }
    }
  }
  costflow();
  cout << -ans << '\n';
  return 0;
}