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,unroll-loops,no-stack-protector")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3005;
map<int, vector<int> > dif;
vector<int> mod[8];
int a[N];
int n;
template <class C, class F>
struct Mcmf {
  static constexpr F eps = (F)1e-9;
  struct Edge {
    int u, v, inv;
    F cap, flow;
    C cost;
    Edge(int u, int v, C cost, F cap, int inv)
        : u(u), v(v), cost(cost), cap(cap), flow(0), inv(inv) {}
  };
  int second, t, tm, n, m = 0;
  vector<vector<Edge> > g;
  vector<Edge*> prev;
  vector<C> cost;
  vector<int> state;
  Mcmf(int n, int ss = -1, int tt = -1)
      : n(n), g(n + 5), cost(n + 5), state(n + 5), prev(n + 5) {
    second = n + 1;
    tm = n + 2;
    t = n + 3;
  }
  void add(int u, int v, C cost, F cap) {
    g[u].push_back(Edge(u, v, cost, cap, int(g[v].size())));
    g[v].push_back(Edge(v, u, -cost, 0, int(g[u].size()) - 1));
    m += 2;
  }
  bool bfs() {
    fill(begin(state), end(state), 2);
    fill(begin(cost), end(cost), numeric_limits<C>::max());
    fill(begin(prev), end(prev), nullptr);
    deque<int> qu;
    qu.push_back(second);
    state[second] = 1, cost[second] = 0;
    while (int(qu.size())) {
      int u = qu.front();
      qu.pop_front();
      state[u] = 0;
      for (Edge& e : g[u])
        if (e.cap - e.flow > eps)
          if (cost[u] + e.cost < cost[e.v]) {
            cost[e.v] = cost[u] + e.cost;
            prev[e.v] = &e;
            if (state[e.v] == 0 ||
                (int(qu.size()) && cost[qu.front()] > cost[e.v]))
              qu.push_front(e.v);
            else if (state[e.v] == 2)
              qu.push_back(e.v);
            state[e.v] = 1;
          }
    }
    return cost[t] != numeric_limits<C>::max();
  }
  pair<C, F> minCostFlow() {
    C cost = 0;
    F flow = 0;
    while (bfs()) {
      F nflow = numeric_limits<F>::max();
      for (Edge* e = prev[t]; e != nullptr; e = prev[e->u])
        nflow = min(nflow, e->cap - e->flow);
      for (Edge* e = prev[t]; e != nullptr; e = prev[e->u]) {
        e->flow += nflow;
        g[e->v][e->inv].flow -= nflow;
        cost += e->cost * nflow;
      }
      flow += nflow;
    }
    return make_pair(cost, flow);
  }
};
int main() {
  cin.tie(0)->sync_with_stdio(0), cout.tie(0);
  cin >> n;
  for (auto i = (0) - ((0) > (n)); i != n - ((0) > (n));
       i += 1 - 2 * ((0) > (n)))
    cin >> a[i];
  Mcmf<int, int> mcmf(2 * n);
  for (auto i = (0) - ((0) > (n)); i != n - ((0) > (n));
       i += 1 - 2 * ((0) > (n))) {
    mcmf.add(mcmf.second, (i), 0, 1);
    mcmf.add((i), (n + (i)), -1, 1);
    mcmf.add((n + (i)), mcmf.tm, 0, 1);
    for (auto j = (i + 1) - ((i + 1) > (n)); j != n - ((i + 1) > (n));
         j += 1 - 2 * ((i + 1) > (n)))
      if (a[i] % 7 == a[j] % 7 || abs(a[i] - a[j]) <= 1)
        mcmf.add((n + (i)), (j), 0, 1);
  }
  mcmf.add(mcmf.tm, mcmf.t, 0, 4);
  auto best = mcmf.minCostFlow();
  ;
  cout << -best.first << '\n';
  return 0;
}