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 N = 3e3 + 1, inf = (1 << 30) - 1, M = 1e5 + 2;
struct MaxCostMaxFlow {
  const static int _V = 4 * N + 2, _E = 20 * N + 2;
  struct Edge {
    int to, c, w, next;
  } E[_E];
  bool inq[_V];
  int s, t, n, adj[_V], d[_V], p[_V];
  queue<int> Q;
  void add(int u, int v, int c, int w) {
    static int ptr = 2;
    E[ptr] = (Edge){v, c, w, adj[u]};
    adj[u] = ptr++;
    E[ptr] = (Edge){u, 0, -w, adj[v]};
    adj[v] = ptr++;
  }
  bool spfa(int& init, int& flow, int& cost) {
    fill_n(d, n, -inf);
    d[s] = 0;
    Q.push(s);
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      inq[u] = false;
      for (int i = adj[u]; i; i = E[i].next) {
        int v = E[i].to;
        if (E[i].c && d[v] < d[u] + E[i].w) {
          d[v] = d[u] + E[i].w;
          p[v] = i;
          if (!inq[v]) inq[v] = true, Q.push(v);
        }
      }
    }
    if (d[t] == -inf) return false;
    int f = init;
    for (int v = t; v != s; v = E[p[v] ^ 1].to) f = min(f, E[p[v]].c);
    for (int v = t; v != s; v = E[p[v] ^ 1].to)
      E[p[v]].c -= f, E[p[v] ^ 1].c += f;
    init -= f, flow += f, cost += f * d[t];
    return true;
  }
  int main(int _s, int _t, int _n, int _i) {
    s = _s, t = _t, n = _n;
    int i = _i, f = 0, c = 0;
    while (i && spfa(i, f, c))
      ;
    return c;
  }
} F;
int a[N], p[7], q[M], x[N], y[N];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = (1), i_end = (n + 1); i < i_end; ++i) {
    scanf("%d", a + i);
    F.add(0, i, 1, 0);
    F.add(i, i + n, 1, 1);
    F.add(i + n, 2 * n + 1, 1, 0);
  }
  int m = 2 * n + 1;
  for (int i = (n), i_end = (1); i >= i_end; --i) {
    x[i] = ++m, y[i] = ++m;
    int& next = p[a[i] % 7];
    if (next) F.add(x[i], next, inf, 0), F.add(i + n, next, 1, 0);
    F.add(next = x[i], i, 1, 0);
    if (q[a[i] + 1]) F.add(i + n, q[a[i] + 1], 1, 0);
    if (q[a[i] - 1]) F.add(i + n, q[a[i] - 1], 1, 0);
    if (q[a[i]]) F.add(y[i], q[a[i]], inf, 0);
    F.add(q[a[i]] = y[i], i, 1, 0);
  }
  printf("%d\n", F.main(0, 2 * n + 1, m + 1, 4));
  return 0;
}