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 = 15005;
const int M = 100005;
const int INF = 0x7f7f7f7f;
struct Edge {
  int from, to, flow, cap, cost;
};
struct mcmf {
  int n, m, s, t;
  vector<Edge> Edges;
  vector<int> g[N];
  int p[N], df[N], w[N];
  bool vis[N];
  void init(int n) {
    this->n = n;
    for (int i = 1; i <= n; i++) g[i].clear();
    Edges.clear();
  }
  void addEdge(int u, int v, int c, int w) {
    Edges.push_back((Edge){u, v, 0, c, w});
    Edges.push_back((Edge){v, u, 0, 0, -w});
    m = Edges.size();
    g[u].push_back(m - 2);
    g[v].push_back(m - 1);
  }
  int spfa() {
    for (int i = 1; i <= n; i++) {
      df[i] = 0;
      vis[i] = 0;
      w[i] = INF;
    }
    queue<int> Q;
    df[s] = INF, vis[s] = 1, w[s] = 0;
    Q.push(s);
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      vis[u] = 0;
      for (auto &x : g[u]) {
        Edge &e = Edges[x];
        if (e.cap > e.flow && w[e.to] > w[u] + e.cost) {
          p[e.to] = x;
          df[e.to] = min(df[e.from], e.cap - e.flow);
          w[e.to] = w[u] + e.cost;
          if (!vis[e.to]) {
            vis[e.to] = 1;
            Q.push(e.to);
          }
        }
      }
    }
    for (int u = t; u != s; u = Edges[p[u]].from) {
      Edges[p[u]].flow += df[t];
      Edges[p[u] ^ 1].flow -= df[t];
    }
    return w[t];
  }
  int mcf(int s, int t) {
    this->s = s;
    this->t = t;
    int F = 0, ret = 0;
    while (F < 4) {
      F++;
      ret -= spfa();
    }
    return ret;
  }
} T;
int n, a[N], lastval[M], lastmod[7];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  T.init(5 * n + 2);
  for (int i = n; i; i--) {
    if (lastval[a[i] + 1]) {
      T.addEdge(n + i, 2 * n + lastval[a[i] + 1], 1, 0);
      T.addEdge(2 * n + i, 2 * n + lastval[a[i] + 1], 1, 0);
    }
    if (lastval[a[i] - 1]) {
      T.addEdge(n + i, 3 * n + lastval[a[i] - 1], 1, 0);
      T.addEdge(3 * n + i, 3 * n + lastval[a[i] - 1], 1, 0);
    }
    lastval[a[i]] = i;
    if (lastmod[a[i] % 7]) {
      T.addEdge(n + i, 4 * n + lastmod[a[i] % 7], 1, 0);
      T.addEdge(4 * n + i, 4 * n + lastmod[a[i] % 7], 1, 0);
    }
    lastmod[a[i] % 7] = i;
  }
  for (int i = 1; i <= n; i++) {
    T.addEdge(i, n + i, 1, -1);
    T.addEdge(5 * n + 1, i, 1, 0);
    T.addEdge(n + i, 5 * n + 2, 1, 0);
    for (int j = 2; j <= 4; j++) T.addEdge(j * n + i, i, 1, 0);
  }
  printf("%d\n", T.mcf(5 * n + 1, 5 * n + 2));
  return 0;
}