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>
const int maxn = 100100;
using std::cin;
using std::cout;
struct T {
  int to, nxt, v, f;
} way[maxn << 1];
int h[maxn], num = 1;
inline void link(int x, int y, int v, int f) {
  way[++num] = {y, h[x], v, f}, h[x] = num;
  way[++num] = {x, h[y], 0, -f}, h[y] = num;
}
int dis[maxn], vis[maxn], fr[maxn];
std::queue<int> q;
inline bool relax(int x, int d) {
  if (d > dis[x]) {
    dis[x] = d;
    if (!vis[x]) vis[x] = 1, q.push(x);
    return true;
  }
  return false;
}
inline int bellmanford(int s, int t) {
  for (int i = s; i <= t; ++i) dis[i] = -1;
  for (relax(s, 0); !q.empty();) {
    int x = q.front();
    q.pop();
    vis[x] = 0;
    for (int i = h[x]; i; i = way[i].nxt)
      if (way[i].v)
        if (relax(way[i].to, dis[x] + way[i].f)) fr[way[i].to] = i;
  }
  return dis[t] >= 0;
}
inline int ek(int s, int t) {
  int ans = 0;
  for (int c = 0; c < 2 && bellmanford(s, t); ++c) {
    ans += dis[t];
    for (int i = t; i != s; i = way[fr[i] ^ 1].to) {
      way[fr[i]].v -= 1;
      way[fr[i] ^ 1].v += 1;
    }
  }
  return ans;
}
int n, tot;
int a[maxn];
int is[maxn];
int flg[7];
inline void add(int& x, int y) {
  int og = x;
  link(x = ++tot, y, 1, 0);
  if (og) link(x, og, 1, 0);
}
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n;
  tot = n + n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    link(0, i, 1, 0);
    link(i, i + n, 1, 1);
    if (is[a[i] - 1]) link(i + n, is[a[i] - 1], 1, 0);
    if (is[a[i] + 1]) link(i + n, is[a[i] + 1], 1, 0);
    if (is[a[i]]) link(i + n, is[a[i]], 1, 0);
    if (flg[a[i] % 7]) link(i + n, flg[a[i] % 7], 1, 0);
    add(is[a[i]], i);
    add(flg[a[i] % 7], i);
  }
  ++tot;
  for (int i = 1; i <= n; ++i) {
    link(i + n, tot, 1, 0);
  }
  cout << ek(0, tot) << '\n';
}