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;
int S, T;
int n;
int wz[100005], las[100005], a[6005];
int head[(6005)], t[(6005 * 100)], next_[(6005 * 100)], v[(6005 * 100)],
    cost[(6005 * 100)], sum;
void ins(int x, int y, int z, int co) {
  t[++sum] = y;
  v[sum] = z;
  cost[sum] = co;
  next_[sum] = head[x];
  head[x] = sum;
}
void insert(int x, int y, int z, int co) {
  ins(x, y, z, co);
  ins(y, x, 0, -co);
}
int dist[(6005)], pre[(6005)];
bool bz[(6005)];
int qu[(6005) * 1000];
bool spfa() {
  memset(dist, 200, sizeof(dist));
  dist[S] = 0;
  int l = 1, r = 1;
  qu[1] = S;
  while (l <= r) {
    int now = qu[l];
    bz[now] = 0;
    for (int tmp = head[now]; tmp; tmp = next_[tmp]) {
      if (v[tmp] == 0) continue;
      if (dist[t[tmp]] < dist[now] + cost[tmp]) {
        dist[t[tmp]] = dist[now] + cost[tmp];
        pre[t[tmp]] = tmp;
        if (!bz[t[tmp]]) {
          bz[t[tmp]] = 1;
          qu[++r] = t[tmp];
          if (dist[qu[l + 1]] < dist[qu[r]]) swap(qu[l + 1], qu[r]);
        }
      }
    }
    l++;
  }
  return dist[T] < 2e8;
}
int ans;
void costflow() {
  for (int i = 1; i <= 4; i++) {
    if (!spfa()) break;
    ans += dist[T];
    int tmp = T;
    while (tmp != S) {
      v[pre[tmp]]--;
      v[pre[tmp] ^ 1]++;
      tmp = t[pre[tmp] ^ 1];
    }
  }
  cout << ans;
}
int main() {
  sum = 1;
  scanf("%d", &n);
  S = 0;
  T = n + n + 1;
  for (int i = 1; i <= n; i++) {
    insert(S, i, 1e9, 0);
    insert(i + n, T, 1e9, 0);
    insert(i, i + n, 1, 1);
    insert(i, i + n, 1e9, 0);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (wz[a[i] - 1]) insert(wz[a[i] - 1] + n, i, 1e9, 0);
    if (wz[a[i] + 1]) insert(wz[a[i] + 1] + n, i, 1e9, 0);
    if (las[a[i] % 7]) insert(las[a[i] % 7] + n, i, 1e9, 0);
    wz[a[i]] = i;
    las[a[i] % 7] = i;
  }
  costflow();
  return 0;
}