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;
char CRTBUFF[30000];
struct debugger {
  static void call(string::iterator it, string::iterator ed) {}
  template <typename T, typename... aT>
  static void call(string::iterator it, string::iterator ed, T a, aT... rest) {
    string b;
    for (; *it != ','; ++it)
      if (*it != ' ') b += *it;
    cout << b << "=" << a << " ";
    call(++it, ed, rest...);
  }
};
struct _mcmf {
  const int INF = 1 << 28;
  int potential[200000], dis[200000], cap[200000], cost[200000];
  int n, m, s, t, to[200000], from[200000], last[200000], next[200000],
      adj[200000];
  void init(int nodes, int source, int sink) {
    m = 0, n = nodes;
    s = source, t = sink;
    for (int i = 0; i <= n; i++) potential[i] = 0, last[i] = -1;
  }
  void add_edge(int u, int v, int w, int c) {
    from[m] = u, adj[m] = v, cap[m] = c, cost[m] = w, next[m] = last[u],
    last[u] = m++;
    from[m] = v, adj[m] = u, cap[m] = 0, cost[m] = -w, next[m] = last[v],
    last[v] = m++;
  }
  pair<int, int> solve() {
    int i, j, e, u, v, c;
    int w, aug = 0, mincost = 0, maxflow = 0;
    for (i = 0; i < n; i++) potential[i] = INF, potential[s] = 0;
    for (u = 0; u < n; u++) {
      for (e = last[u]; e != -1; e = next[e]) {
        v = adj[e];
        potential[v] = min(potential[v], potential[u] + cost[e]);
      }
    }
    while (1) {
      priority_queue<pair<int, int>, vector<pair<int, int> >,
                     greater<pair<int, int> > >
          Q;
      for (i = 0; i < n; i++) dis[i] = INF;
      dis[s] = 0;
      Q.push({dis[s], s});
      while (!Q.empty()) {
        c = Q.top().first, u = Q.top().second;
        Q.pop();
        if (c > dis[u]) continue;
        for (e = last[u]; e != -1; e = next[e]) {
          if (cap[e] != 0) {
            v = adj[e];
            w = dis[u] + potential[u] + cost[e] - potential[v];
            if (dis[v] > w) {
              dis[v] = w, to[v] = e;
              Q.push({dis[v], v});
            }
          }
        }
      }
      if (dis[t] >= (INF >> 1)) break;
      aug = cap[to[t]];
      for (i = t; i != s; i = from[to[i]]) aug = min(aug, cap[to[i]]);
      for (i = t; i != s; i = from[to[i]]) {
        cap[to[i]] -= aug;
        cap[to[i] ^ 1] += aug;
        mincost += (cost[to[i]] * aug);
      }
      for (i = 0; i <= n; i++) potential[i] = min(potential[i] + dis[i], INF);
      maxflow += aug;
    }
    return make_pair(mincost, maxflow);
  }
} mcmf;
int A[200000 + 100];
int Pos[200000 + 10], PMod[200000 + 10];
int main() {
  {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  };
  int n;
  while (cin >> n) {
    int INF = 1000000000;
    memset(PMod, -1, sizeof(PMod));
    memset(Pos, -1, sizeof(Pos));
    for (int i = (0); i < (n); i += (1)) cin >> A[i];
    int lst = n;
    int src = lst++;
    int sink = lst++;
    mcmf.init(6 * n + 6, 2 * src + 1, 2 * sink + 2);
    mcmf.add_edge(2 * src + 1, 2 * src + 2, 0, 4);
    mcmf.add_edge(2 * sink + 1, 2 * sink + 2, 0, 4);
    for (int i = n - 1; i >= 0; i--) {
      int e[3] = {Pos[A[i] - 1], Pos[A[i] + 1], PMod[A[i] % 7]};
      for (int j = (0); j < (3); j += (1)) {
        if (e[j] == -1) continue;
        mcmf.add_edge(2 * i + 2, 2 * e[j] + 1, 0, INF);
      }
      int x = lst++, y = lst++;
      if (Pos[A[i]] != -1) mcmf.add_edge(2 * x + 1, 2 * Pos[A[i]] + 1, 0, INF);
      if (PMod[A[i] % 7] != -1)
        mcmf.add_edge(2 * y + 1, 2 * PMod[A[i] % 7] + 1, 0, INF);
      mcmf.add_edge(2 * x + 1, 2 * i + 1, 0, INF);
      mcmf.add_edge(2 * y + 1, 2 * i + 1, 0, INF);
      mcmf.add_edge(2 * src + 2, 2 * i + 1, 0, INF);
      mcmf.add_edge(2 * i + 2, 2 * sink + 1, 0, INF);
      mcmf.add_edge(2 * i + 1, 2 * i + 2, -1, 1);
      Pos[A[i]] = x, PMod[A[i] % 7] = y;
    }
    int cost, flow;
    tie(cost, flow) = mcmf.solve();
    int ans = -cost;
    cout << ans << "\n";
  }
  return 0;
}