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("O3,unroll-loops,no-stack-protector")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dis(1, 1000);
const int N = 3005;
int n, note[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;
    t = n + 2;
    tm = 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), 0);
    fill(begin(cost), end(cost), numeric_limits<C>::max());
    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] = 2;
      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] == 2 ||
                (int(qu.size()) && cost[qu.front()] > cost[e.v]))
              qu.push_front(e.v);
            else if (state[e.v] == 0)
              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);
  while (cin >> n) {
    Mcmf<int, int> g(2 * n + 5);
    for (auto i = (1) - ((1) > (n + 1)); i != n + 1 - ((1) > (n + 1));
         i += 1 - 2 * ((1) > (n + 1))) {
      cin >> note[i];
      g.add(g.second, i, 0, 1);
      g.add(i, i + n, -1, 1);
      g.add(i + n, g.tm, 0, 1);
    }
    for (auto i = (1) - ((1) > (n + 1)); i != n + 1 - ((1) > (n + 1));
         i += 1 - 2 * ((1) > (n + 1)))
      for (auto j = (i + 1) - ((i + 1) > (n + 1));
           j != n + 1 - ((i + 1) > (n + 1)); j += 1 - 2 * ((i + 1) > (n + 1)))
        if ((abs(note[j] - note[i]) <= 1) || (note[j] % 7 == note[i] % 7))
          g.add(i + n, j, 0, 1);
    g.add(g.tm, g.t, 0, 4);
    auto res = g.minCostFlow();
    cout << -res.first << '\n';
  }
  return 0;
}