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;
const long long mod = 1e9 + 7;
const long long inf = 1e9 + 7;
const double eps = 1e-9;
struct flowEdge {
  int u, v;
  long long c, f, cost;
  flowEdge(int u, int v, long long c, long long cost)
      : u(u), v(v), c(c), f(0), cost(cost) {}
};
struct mcf {
  int n, m, s, t;
  vector<flowEdge> e;
  vector<int> g[6005];
  bool inq[6005];
  long long d[6005];
  int p[6005];
  const long long inf = 4e18;
  void init(int n) {
    this->n = n;
    m = 0;
    e.clear();
    for (int i = 0; i <= n; ++i) g[i].clear();
  }
  void addEdge(int u, int v, long long c, long long cost) {
    g[u].push_back(e.size());
    e.emplace_back(u, v, c, cost);
    g[v].push_back(e.size());
    e.emplace_back(v, u, 0, -cost);
    m = e.size();
  }
  bool spfa() {
    for (int i = 0; i <= n; ++i) d[i] = inf, p[i] = -1, inq[i] = false;
    queue<int> q;
    q.push(s);
    inq[s] = true;
    d[s] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      inq[u] = false;
      for (auto id : g[u]) {
        int v = e[id].v;
        long long w = e[id].cost;
        if (e[id].c - e[id].f >= 1 && d[u] + w < d[v]) {
          p[v] = id;
          d[v] = d[u] + w;
          if (!inq[v]) q.push(v), inq[v] = true;
        }
      }
    }
    return d[t] != inf;
  }
  long long mncost(int s, int t, long long k) {
    this->s = s;
    this->t = t;
    long long totflow = 0, totcost = 0;
    while (totflow < k) {
      if (!spfa()) break;
      long long flow = k - totflow;
      for (int cur = t; cur != s; cur = e[p[cur]].u)
        flow = min(flow, e[p[cur]].c - e[p[cur]].f);
      totflow += flow;
      totcost += flow * d[t];
      for (int cur = t; cur != s; cur = e[p[cur]].u) {
        e[p[cur]].f += flow;
        e[p[cur] ^ 1].f -= flow;
      }
    }
    return (totflow < k) ? -1 : totcost;
  }
} ds;
int n;
int a[3005];
int val[100005], m[7];
void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  ds.init(2 * n + 2);
  memset(val, -1, sizeof(val));
  memset(m, -1, sizeof(m));
  for (int i = n; i >= 1; --i) {
    if (val[a[i] + 1] != -1) {
      int idx = val[a[i] + 1];
      ds.addEdge(2 * i + 1, 2 * idx, ds.inf, 0);
      ds.addEdge(2 * i + 1, 2 * idx + 1, 1, 0);
    }
    if (val[a[i] - 1] != -1) {
      int idx = val[a[i] - 1];
      ds.addEdge(2 * i + 1, 2 * idx, ds.inf, 0);
      ds.addEdge(2 * i + 1, 2 * idx + 1, 1, 0);
    }
    if (m[a[i] % 7] != -1) {
      int idx = m[a[i] % 7];
      ds.addEdge(2 * i + 1, 2 * idx, ds.inf, 0);
      ds.addEdge(2 * i + 1, 2 * idx + 1, 1, 0);
    }
    val[a[i]] = m[a[i] % 7] = i;
  }
  for (int i = 1; i <= n; ++i) {
    ds.addEdge(0, 2 * i, 1, 0);
    ds.addEdge(2 * i, 2 * i + 1, 1, -1);
    ds.addEdge(2 * i + 1, 2 * n + 2, 1, 0);
  }
  cout << -ds.mncost(0, 2 * n + 2, 4);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int test = 1;
  for (int tc = 1; tc <= test; ++tc) solve();
  return 0;
}