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;
long long INF = 1LL << 60;
long long MOD = 1e9 + 7;
namespace output {
void pr(short x) { cout << x; }
void pr(signed x) { cout << x; }
void pr(long x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(unsigned short x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(long double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(bool x) { cout << x; }
template <size_t sz>
void pr(const bitset<sz>& x) {
  cout << x;
}
template <class T>
void pr(const complex<T>& x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T1, class T2, class T3>
void pr(const tuple<T1, T2, T3>& x);
template <class T>
void pr(const T& x);
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("(", x.first, ", ", x.second, ")");
}
template <class T1, class T2, class T3>
void pr(const tuple<T1, T2, T3>& x) {
  pr("(", get<0>(x), ", ", get<1>(x), ", ", get<2>(x), ")");
}
template <class T>
void pr(const T& x) {
  pr("[");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("]");
}
void print() { pr("\n"); }
template <class T, class... Ts>
void print(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  print(ts...);
}
}  // namespace output
using namespace output;
template <class T1, class T2>
istream& operator>>(istream& is, pair<T1, T2>& x) {
  is >> x.first >> x.second;
  return is;
}
template <class T1, class T2, class T3>
istream& operator>>(istream& is, tuple<T1, T2, T3>& x) {
  is >> get<0>(x) >> get<1>(x) >> get<2>(x);
  return is;
}
template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (auto& x : v) is >> x;
  return is;
}
int powa(int base, int exp) {
  int res = 1;
  while (exp) {
    if (exp & 1) res = res * base % MOD;
    base = base * base % MOD;
    exp >>= 1;
  }
  return res;
}
bool mini(int& a, int b) { return b < a ? a = b, 1 : 0; }
bool maxi(int& a, int b) { return b > a ? a = b, 1 : 0; }
signed main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  cin >> a;
  const int BIG = 1e5 + 5;
  int m = 4 * n + 2;
  int source = 4 * n;
  int sink = 4 * n + 1;
  vector<vector<int> > adj(m, vector<int>(m));
  vector<int> lastm(7, -1);
  vector<int> last(BIG, -1);
  vector<pair<int, int> > edges;
  auto addedge = [&](int u, int v, int w = 1) {
    adj[u][v] = w;
    edges.emplace_back(u, v);
  };
  for (int(i) = (0); (i) < (n); ++(i)) {
    addedge(source, i);
    addedge(i, n + i);
    addedge(n + i, sink);
    addedge(n + i, 2 * n + i);
    addedge(3 * n + i, i);
    if (last[a[i]] != -1) {
      addedge(3 * n + last[a[i]], 3 * n + i, 4);
    }
    if (last[a[i] - 1] != -1) {
      addedge(n + last[a[i] - 1], 3 * n + i);
    }
    if (last[a[i] + 1] != -1) {
      addedge(n + last[a[i] + 1], 3 * n + i);
    }
    if (lastm[a[i] % 7] != -1) {
      addedge(2 * n + lastm[a[i] % 7], 2 * n + i, 4);
      addedge(2 * n + lastm[a[i] % 7], i);
    }
    last[a[i]] = i;
    lastm[a[i] % 7] = i;
  }
  int res = 0;
  for (int(flow) = (0); (flow) < (4); ++(flow)) {
    vector<int> par(m), dist(m, 1);
    dist[source] = 0;
    for (int(p) = (0); (p) < (m); ++(p)) {
      bool something = false;
      for (pair<int, int> edge : edges) {
        int u, v;
        tie(u, v) = edge;
        if (!adj[u][v] || dist[u] == 1) continue;
        int c = 0;
        if (u < n && v == n + u)
          c = -1;
        else if (v < n && u == n + v)
          c = 1;
        if (dist[u] + c < dist[v]) {
          something = true;
          dist[v] = dist[u] + c;
          par[v] = u;
        }
      }
      if (!something) break;
      assert(p < m - 1);
    }
    res -= dist[sink];
    int x = sink;
    while (x != source) {
      --adj[par[x]][x];
      ++adj[x][par[x]];
      edges.emplace_back(x, par[x]);
      x = par[x];
    }
  }
  print(res);
}