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;
void ga(int N, int *A) {
  for (int i(0); i < N; i++) scanf("%d", A + i);
}
template <class FW = long long, class CO = long long>
struct MCMF {
  struct eg {
    int t;
    FW C;
    CO W;
    int x;
  };
  const FW IF = 1e9;
  const CO IC = 1e17;
  int n, t, S, T;
  FW s;
  CO P;
  vector<int> l, v;
  vector<CO> H;
  vector<eg> G;
  MCMF(int n) : n(n), l(n, -1), v(n, 0), H(n, 0) { t = s = P = 0, G.clear(); }
  int ade(int F, int T, FW C, CO W) {
    return G.push_back({T, C, W, l[F]}),
           l[F] = t++, G.push_back({F, 0, -W, l[T]}), l[T] = t++, t - 2;
  }
  pair<FW, CO> mf(int a, int b) {
    S = a, T = b, SPFA();
    do do
        for (int i(0); i < n; i++) v[i] = 0;
      while (FLW(S, IF));
    while (ML());
    return {s, P};
  }
  void SPFA() {
    for (int i(0); i < n; i++) H[i] = IC;
    priority_queue<pair<CO, long long>> Q;
    Q.push({H[S] = 0, S});
    while (!Q.empty()) {
      long long x = Q.top().second;
      CO d = -Q.top().first;
      Q.pop();
      if (H[x] != d) continue;
      for (int i = l[x]; ~i; i = G[i].x)
        if (G[i].C > 0 && H[G[i].t] > d + G[i].W)
          Q.push({-(H[G[i].t] = d + G[i].W), G[i].t});
    }
    for (int i(0); i < n; i++) H[i] = H[T] - H[i];
  }
  FW FLW(long long x, FW f) {
    if (x == T) return P += H[S] * f, s += f, f;
    FW t = f;
    v[x] = 1;
    for (int i = l[x]; ~i; i = G[i].x)
      if (G[i].C && !v[G[i].t] && H[G[i].t] + G[i].W == H[x]) {
        FW a = FLW(G[i].t, min(t, G[i].C));
        G[i].C -= a, G[i ^ 1].C += a, t -= a;
        if (!t) break;
      }
    return f - t;
  }
  bool ML() {
    CO d = IC;
    for (int i(0); i < n; i++)
      if (v[i])
        for (int j = l[i]; ~j; j = G[j].x)
          if (G[j].C && !v[G[j].t]) d = min(d, H[G[j].t] + G[j].W - H[i]);
    if (d == IC) return 0;
    for (int i(0); i < n; i++)
      if (v[i]) H[i] += d;
    return 1;
  }
};
int N, A[(3006)], H;
int main(void) {
  scanf("%d", &N), ga(N, A);
  MCMF<long long, long long> G(2 * N + 3);
  G.ade(2 * N, 2 * N + 2, 4, 0);
  for (int i(0); i < N; i++)
    G.ade(2 * N + 2, i, 1, 0), G.ade(i, N + i, 1, -1),
        G.ade(N + i, 2 * N + 1, 1, 0);
  for (int i(0); i < N; i++) {
    H = 4;
    for (int k(i + 1); k < N && H; k++)
      if (A[i] + 1 == A[k]) G.ade(N + i, k, 1, 0), --H;
    H = 4;
    for (int k(i + 1); k < N && H; k++)
      if (A[i] - 1 == A[k]) G.ade(N + i, k, 1, 0), --H;
    H = 4;
    for (int k(i + 1); k < N && H; k++)
      if (A[i] % 7 == A[k] % 7) G.ade(N + i, k, 1, 0), --H;
  }
  printf("%lld\n", -G.mf(2 * N, 2 * N + 1).second);
  return 0;
}