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 = (int)1e6;
struct edge {
  int to, cap, cost;
};
struct flow {
  vector<edge> e;
  int n, s, t;
  vector<vector<int> > g;
  flow(int n_) : n(n_), s(n_ - 2), t(n_ - 1), g(n_) {}
  void add_edge(int from, int to, int cap, int cost) {
    g[from].push_back((int)(e).size());
    e.push_back(edge{to, cap, cost});
    g[to].push_back((int)(e).size());
    e.push_back(edge{from, 0, -cost});
  }
  vector<int> pot;
  void prepare() {
    vector<int> order(n);
    order[0] = s, order.back() = t;
    for (int i = 0; i < (int)(s); ++i)
      if (i) order[i + 1] = i;
    vector<int> in(n);
    for (int i = 0; i < (int)(n); ++i) in[order[i]] = i;
    pot = vector<int>(n, inf);
    pot[order[0]] = 0;
    for (int v : order)
      for (int num : g[v])
        if (e[num].cap > 0) {
          int to = e[num].to, cost = e[num].cost;
          assert(in[to] > in[v]);
          pot[to] = min(pot[to], cost + pot[v]);
        }
  }
  int push_flow() {
    for (int i = 0; i < (int)(n); ++i)
      for (int num : g[i])
        if (e[num].cap > 0) assert(e[num].cost + pot[i] - pot[e[num].to] >= 0);
    vector<int> dist(n, inf), pred(n, -1), pedge(n, -1);
    vector<char> used(n);
    dist[s] = 0;
    for (int it = 0; it < (int)(n); ++it) {
      int who = -1, best = inf;
      for (int i = 0; i < (int)(n); ++i)
        if (!used[i] && dist[i] < best) {
          best = dist[i];
          who = i;
        }
      used[who] = 1;
      for (int num : g[who])
        if (e[num].cap > 0) {
          int to = e[num].to, cost = e[num].cost;
          int len = pot[who] - pot[to] + cost + dist[who];
          if (dist[to] > len) {
            dist[to] = len;
            pred[to] = who;
            pedge[to] = num;
          }
        }
    }
    int ans = dist[t] + (pot[t] - pot[s]);
    for (int i = 0; i < (int)(n); ++i) pot[i] += dist[i];
    assert(dist[t] < inf);
    int cur = t;
    while (cur != s) {
      e[pedge[cur]].cap--;
      e[pedge[cur] ^ 1].cap++;
      cur = pred[cur];
    }
    return ans;
  }
  int mincost(int flw) {
    int ans = 0;
    prepare();
    for (int it = 0; it < (int)(flw); ++it) {
      ans += push_flow();
      if (ans == -(n - 2) / 2) return ans;
    }
    return ans;
  }
};
bool match(int tp, int what) {
  if (tp == 0) return what == -1;
  if (tp == 1) return what == +1;
  return what % 7 == 0;
}
void solve(int n) {
  vector<int> a(n);
  for (int i = 0; i < (int)(n); ++i) cin >> a[i];
  flow f(2 * n + 2);
  for (int i = 0; i < (int)(n); ++i)
    for (int type = 0; type < (int)(3); ++type) {
      int it = 0;
      for (int j = i + 1; j < n; j++)
        if (match(type, a[i] - a[j])) {
          f.add_edge(2 * i + 1, 2 * j, 1, 0);
          ++it;
        }
    }
  for (int i = 0; i < (int)(n); ++i) {
    f.add_edge(f.s, 2 * i, 1, 0);
    f.add_edge(2 * i, 2 * i + 1, 1, -1);
    f.add_edge(2 * i + 1, f.t, 1, 0);
  }
  const int ans = -f.mincost(4);
  assert(4 <= ans && ans <= n);
  cout << ans << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  while (cin >> n) solve(n);
}