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...);
  }
};
using namespace std;
struct _mcmf {
  struct edge_t {
    int u, v, w, cap, prev;
  };
  static const int NMAX = 30000;
  static const int NINF = 1000000;
  vector<edge_t> edges;
  int last[NMAX];
  int D[NMAX];
  int E[NMAX];
  void reset() {
    edges.clear();
    memset(last, -1, sizeof(last));
  }
  void add_edge(int u, int v, int w, int cap) {
    edges.push_back({u, v, w, cap, last[u]});
    last[u] = edges.size() - 1;
    edges.push_back({v, u, -w, 0, last[v]});
    last[v] = edges.size() - 1;
  }
  bool spfa(int src, int sink) {
    for (int u = 0; u < NMAX; u++) D[u] = NINF, E[u] = -1;
    queue<int> que;
    for (int u = 0; u < NMAX; u++) que.push(u);
    D[src] = 0;
    E[src] = -2;
    que.push(src);
    while (!que.empty()) {
      int u = que.front();
      que.pop();
      for (int i = last[u]; i != -1; i = edges[i].prev) {
        int v = edges[i].v, w = edges[i].w;
        if (edges[i].cap && (E[v] == -1 || D[u] + w < D[v])) {
          D[v] = D[u] + w;
          E[v] = i;
          que.push(v);
        }
      }
    }
    return (E[sink] != -1);
  }
  pair<int, int> max_flow(int src, int sink) {
    int mflow = 0;
    int mcost = 0;
    while (spfa(src, sink)) {
      int flow = NINF;
      for (int i = E[sink]; i >= 0; i = E[edges[i].u]) {
        flow = min(flow, edges[i].cap);
      }
      for (int i = E[sink]; i >= 0; i = E[edges[i].u]) {
        edges[i].cap -= flow;
        edges[i ^ 1].cap += flow;
        mcost += edges[i].w * flow;
      }
      mflow += flow;
    }
    return {mcost, mflow};
  }
} 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) {
    mcmf.reset();
    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.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, 10000000);
      }
      int x = lst++, y = lst++;
      if (Pos[A[i]] != -1)
        mcmf.add_edge(2 * x + 1, 2 * Pos[A[i]] + 1, 0, 10000000);
      if (PMod[A[i] % 7] != -1)
        mcmf.add_edge(2 * y + 1, 2 * PMod[A[i] % 7] + 1, 0, 10000000);
      mcmf.add_edge(2 * x + 1, 2 * i + 1, 0, 10000000);
      mcmf.add_edge(2 * y + 1, 2 * i + 1, 0, 10000000);
      mcmf.add_edge(2 * src + 2, 2 * i + 1, 0, 10000000);
      mcmf.add_edge(2 * i + 2, 2 * sink + 1, 0, 10000000);
      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.max_flow(2 * src + 1, 2 * sink + 2);
    int ans = -cost;
    cout << ans << "\n";
  }
  return 0;
}