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 = 50010;
const int inf = 1e9;
inline int read() {
  int p = 0;
  int f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    p = p * 10 + ch - '0';
    ch = getchar();
  }
  return p * f;
}
struct node {
  int x, y, d, c, next;
} edge[N << 4];
int len, first[N];
void ins(int x, int y, int c, int d) {
  len++;
  edge[len].x = x;
  edge[len].y = y;
  edge[len].c = c;
  edge[len].d = d;
  edge[len].next = first[x];
  first[x] = len;
  len++;
  edge[len].x = y;
  edge[len].y = x;
  edge[len].c = 0;
  edge[len].d = -d;
  edge[len].next = first[y];
  first[y] = len;
}
bool v[N];
int d[N];
queue<int> q;
int pre[N], pos[N];
int s, t;
bool bfs() {
  while (!q.empty()) q.pop();
  q.push(s);
  memset(d, -63, sizeof(d));
  d[s] = 0;
  memset(v, 0, sizeof(v));
  v[s] = 1;
  while (!q.empty()) {
    int x = q.front();
    for (int k = first[x]; k != -1; k = edge[k].next) {
      int y = edge[k].y;
      if (d[y] < d[x] + edge[k].d && edge[k].c) {
        d[y] = d[x] + edge[k].d;
        pos[y] = x;
        pre[y] = k;
        if (!v[y]) {
          v[y] = 1;
          q.push(y);
        }
      }
    }
    q.pop();
    v[x] = 0;
  }
  return d[t] >= 0;
}
int n, a[N];
int main() {
  len = 1;
  memset(first, -1, sizeof(first));
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  int ss = 2 * n + 1;
  s = ss + 1;
  t = s + 1;
  ins(s, ss, 4, 0);
  for (int i = 1; i <= n; i++) {
    ins(ss, i + n, 1, 0);
    ins(i + n, i, 1, 1);
    ins(i, t, 1, 0);
  }
  for (int i = 1; i <= n; i++) {
    int cnt = 0;
    for (int j = i + 1; j <= n; j++)
      if ((a[i] - a[j] == 1) && cnt < 1) {
        ins(i, j + n, inf, 0);
        cnt++;
      }
    cnt = 0;
    for (int j = i + 1; j <= n; j++)
      if ((a[i] - a[j] == -1) && cnt < 1) {
        ins(i, j + n, inf, 0);
        cnt++;
      }
    cnt = 0;
    for (int j = i + 1; j <= n; j++)
      if ((a[i] % 7 == a[j] % 7) && cnt < 1) {
        ins(i, j + n, inf, 0);
        cnt++;
      }
    ins(i + n, i, inf, 0);
  }
  int ans = 0;
  while (bfs()) {
    for (int i = t; i != s; i = pos[i])
      ans += edge[pre[i]].d, edge[pre[i]].c--, edge[pre[i] ^ 1].c++;
  }
  return printf("%d\n", ans), 0;
}