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);
}
struct MCMF {
  MCMF() { m = 0; }
  void CLR(int N, int S, int T) {
    m = 0, n = N, s = S + 1, t = T + 1;
    for (int i(0); i < n; i++) g[i + 1].clear();
  }
  void RST() {
    for (int i(0); i < m; i++) E[i].F = 0;
  }
  void ade(int f, int t, int F, int C) {
    E[m++] = eg(++f, ++t, 0, F, C);
    E[m++] = eg(t, f, 0, 0, -C);
    g[f].push_back(m - 2);
    g[t].push_back(m - 1);
  }
  struct eg {
    int f, t, F, C, W;
    eg(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0) {
      f = a, t = b, C = d, W = e, F = c;
    }
    inline int OT(int u) { return f ^ t ^ u; }
  };
  bool C[(6005)];
  int n, m, s, t, p[(6005)], D[(6005)], P[(6005)];
  vector<int> g[(6005)];
  eg E[2 * ((6005) * 10)];
  priority_queue<pair<int, int> > Q;
  int BF(int u) {
    if (C[u]) return p[u];
    if (u == s) return p[s] = 0;
    C[u] = 1, p[u] = int(1e9 + 1);
    for (auto h : g[u])
      if (E[h ^ 1].F < E[h ^ 1].C)
        p[u] = min(p[u], BF(E[h ^ 1].OT(u)) + E[h ^ 1].W);
    return p[u];
  }
  bool DJ() {
    int u, OT, W;
    memset(C, 0, n + 1), fill(D + 1, D + n + 1, int(1e9 + 1)), D[s] = 0;
    Q.push({0, s});
    while (!Q.empty()) {
      u = Q.top().second, Q.pop();
      if (C[u]++) continue;
      for (auto h : g[u]) {
        OT = E[h].OT(u), W = E[h].W + p[u] - p[OT];
        if (E[h].F < E[h].C && D[u] + W < D[OT])
          D[OT] = D[u] + W, P[OT] = h, Q.push({-D[OT], OT});
      }
    }
    for (int i(0); i < n; i++) D[i + 1] += p[i + 1] - p[s];
    return C[t];
  }
  pair<int, int> mf() {
    memset(p, 0, (n + 1) << 2), BF(t);
    int F = 0, W = 0, u, X, S;
    while (DJ()) {
      u = t, X = int(1e9 + 1), S = 0;
      while (u ^ s)
        X = min(X, E[P[u]].C - E[P[u]].F), S += E[P[u]].W, u = E[P[u]].OT(u);
      u = t;
      while (u ^ s) E[P[u]].F += X, E[P[u] ^ 1].F -= X, u = E[P[u]].OT(u);
      F += X, W += X * S;
      memcpy(p, D, (n + 1) << 2);
    }
    return {F, W};
  }
} G;
int N, A[(6005)], H;
int main(void) {
  scanf("%d", &N), ga(N, A), G.CLR(N * 2 + 3, 2 * N, 2 * N + 1), G.RST();
  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("%d\n", -G.mf().second);
  return 0;
}