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 int inf = 1000000007;
const int maxn = 3007;
struct edge {
  int to, w, c, f, rev;
};
map<int, int> le;
vector<edge> g[3 * maxn];
pair<int, int> from[3 * maxn];
int d[3 * maxn], p[3 * maxn];
int a[maxn], lm[10], n, s, t;
void addEdge(int v, int u, int w, int c) {
  int rv = (int)g[v].size(), ru = (int)g[u].size();
  g[v].push_back({u, w, c, 0, ru});
  g[u].push_back({v, -w, 0, 0, rv});
}
int main() {
  scanf("%d", &n);
  int s = 0, t = 3 * n + 1, flow = 0, cost = 0;
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  for (int i = n; i >= 1; --i) {
    int c = a[i];
    addEdge(s, 3 * i - 1, 0, 1);
    addEdge(3 * i - 2, 3 * i - 1, 0, inf);
    addEdge(3 * i - 1, 3 * i, -1, 1);
    addEdge(3 * i, t, 0, 1);
    int ie = le[c], ig = le[c + 1], il = le[c - 1], im = lm[c % 7];
    if (ie) addEdge(3 * i - 1, 3 * ie - 1, 0, inf);
    if (ig && (ig < ie || !ie)) addEdge(3 * i, 3 * ig - 1, 0, 1);
    if (il && (il < ie || !ie)) addEdge(3 * i, 3 * il - 1, 0, 1);
    if (im)
      addEdge(3 * i, 3 * im - 2, 0, 1), addEdge(3 * i - 2, 3 * im - 2, 0, inf);
    le[c] = lm[c % 7] = i;
  }
  fill(p, p + 3 * maxn, inf), p[s] = 0;
  for (int v = 0; v <= 3 * n; ++v)
    for (edge e : g[v])
      if (e.to > v) p[e.to] = min(p[e.to], p[v] + e.w);
  while (flow < 4) {
    fill(d, d + 3 * maxn, inf), fill(from, from + 3 * maxn, make_pair(-1, -1));
    d[s] = 0;
    set<pair<int, int> > q;
    q.insert(make_pair(d[s], s));
    while (!q.empty()) {
      int v = q.begin()->second;
      q.erase(q.begin());
      for (edge e : g[v]) {
        int u = e.to, w = e.w + p[v] - p[u];
        if (e.f < e.c && d[v] + w < d[u]) {
          q.erase(make_pair(d[u], u));
          d[u] = d[v] + w;
          from[u] = make_pair(v, e.rev);
          q.insert(make_pair(d[u], u));
        }
      }
    }
    if (d[t] == inf) break;
    int af = inf;
    for (int v = t; v != s; v = from[v].first) {
      int pv = from[v].first;
      edge *e = &g[pv][g[v][from[v].second].rev];
      af = min(af, e->c - e->f);
    }
    for (int v = t; v != s; v = from[v].first) {
      int pv = from[v].first;
      int vr = from[v].second;
      int pvr = g[v][vr].rev;
      g[v][vr].f -= af;
      g[pv][pvr].f += af;
      cost += af * g[pv][pvr].w;
    }
    for (int i = t; i > 0; --i)
      if (d[i] != inf) p[i] += d[i];
    flow += af;
  }
  printf("%d\n", -cost);
  return 0;
}