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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using std::abs;
using std::cerr;
using std::cin;
using std::cout;
using std::map;
using std::max;
using std::min;
using std::pair;
using std::set;
using std::string;
using std::swap;
using std::vector;
using ll = long long;
using uint = unsigned int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
void _dbg(const char* _s, T _h) {
  cerr << _s << " = " << _h << "\n";
}
template <typename T, typename... Ts>
void _dbg(const char* _s, T _h, Ts... _t) {
  int _b = 0;
  while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',') cerr << *_s++;
  cerr << " = " << _h << ",";
  _dbg(_s + 1, _t...);
}
struct init {
  init() {
    cin.tie(0);
    std::iostream::sync_with_stdio(0);
    cout << std::fixed << std::setprecision(10);
    cerr << std::fixed << std::setprecision(5);
  }
  ~init() {}
} init;
const int MAXN = 11111, INF = 1e9 + 7;
int a[MAXN];
struct edge {
  int from, to, flow, capacity, cost;
  edge(int _from, int _to, int _capacity, int _cost)
      : from(_from), to(_to), flow(0), capacity(_capacity), cost(_cost) {}
};
vector<int> g[MAXN];
vector<edge> es;
void add_edge(int from, int to, int capacity, int cost) {
  es.emplace_back(from, to, capacity, cost);
  g[from].emplace_back(es.size() - 1);
  es.emplace_back(to, from, 0, -cost);
  g[to].emplace_back(es.size() - 1);
}
int phi[MAXN], dist[MAXN];
void bellmanford(int n, int start) {
  std::fill(dist + 1, dist + n + 1, INF);
  dist[start] = 0;
  for (int i = 1; i < n; ++i)
    for (edge e : es)
      if (e.capacity && dist[e.to] > dist[e.from] + e.cost)
        dist[e.to] = dist[e.from] + e.cost;
}
int from[MAXN];
vector<int> johnson(int n, int start, int finish) {
  std::fill(dist + 1, dist + n + 1, INF);
  std::fill(from + 1, from + n + 1, -1);
  dist[start] = 0;
  set<pii> s;
  s.insert({0, start});
  while (!s.empty()) {
    auto p = *(s.begin());
    s.erase(s.begin());
    if (dist[p.second] != p.first) continue;
    for (int x : g[p.second]) {
      edge& e = es[x];
      if (e.flow < e.capacity &&
          dist[e.to] > dist[p.second] + phi[p.second] + e.cost - phi[e.to]) {
        s.erase({dist[e.to], e.to});
        dist[e.to] = dist[p.second] + phi[p.second] + e.cost - phi[e.to];
        s.insert({dist[e.to], e.to});
        from[e.to] = x;
      }
    }
  }
  vector<int> ans;
  if (dist[finish] == INF) return ans;
  while (finish != start) {
    ans.emplace_back(from[finish]);
    finish = es[from[finish]].from;
  }
  for (int i = 1; i <= n; i++) phi[i] += dist[i];
  reverse(ans.begin(), ans.end());
  return ans;
}
bool mincost(int n, int s, int t, int k) {
  bellmanford(n, s);
  for (int i = 0; i < k; i++) {
    vector<int> way = johnson(n, s, t);
    if (way.empty()) return 0;
    for (int x : way) {
      ;
      es[x].flow++;
      es[x ^ 1].flow--;
    };
  }
  return 1;
}
int main() {
  int n;
  cin >> n;
  int k = 4;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    int p = 4;
    for (int j = i - 1; p && j >= 0; --j)
      if (a[j] == a[i] - 1) {
        add_edge(2 * j + 1, 2 * i, 1, 0);
        p--;
      }
    p = 4;
    for (int j = i - 1; p && j >= 0; --j)
      if (a[j] == a[i] + 1) {
        add_edge(2 * j + 1, 2 * i, 1, 0);
        p--;
      }
    p = 4;
    for (int j = i - 1; p && j >= 0; --j)
      if (a[j] % 7 == a[i] % 7) {
        add_edge(2 * j + 1, 2 * i, 1, 0);
        p--;
      }
    add_edge(1, 2 * i, 1, 0);
    add_edge(2 * i, 2 * i + 1, 1, -1);
    add_edge(2 * i + 1, 2 * n + 2, 1, 0);
  }
  mincost(2 * n + 3, 1, 2 * n + 2, k);
  int sum = 0;
  for (int i = 0; i < k; ++i) {
    int v = 1;
    while (v != 2 * n + 2) {
      for (int x : g[v]) {
        edge& e = es[x];
        if (e.flow > 0) {
          sum += e.cost;
          e.flow--;
          es[x ^ 1].flow++;
          v = e.to;
          break;
        }
      }
    }
  }
  cout << -sum << '\n';
  return 0;
}