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 = 0x3f3f3f3f;
const int mm = 66666;
const int maxn = 9999;
int node, src, dest, edge;
int ver[mm], flow[mm], cst[mm], nxt[mm];
int head[maxn], work[maxn], dis[maxn], q[maxn];
int tot_cost;
void prepare(int _node, int _src, int _dest) {
  node = _node, src = _src, dest = _dest;
  for (int i = 0; i < node; ++i) head[i] = -1;
  edge = 0;
  tot_cost = 0;
}
void addedge(int u, int v, int c, int cost) {
  ver[edge] = v, flow[edge] = c, nxt[edge] = head[u], cst[edge] = cost,
  head[u] = edge++;
  ver[edge] = u, flow[edge] = 0, nxt[edge] = head[v], cst[edge] = -cost,
  head[v] = edge++;
}
int ins[maxn];
int pre[maxn];
bool Dinic_spfa() {
  memset(ins, 0, sizeof(ins));
  memset(dis, inf, sizeof(dis));
  memset(pre, -1, sizeof(pre));
  queue<int> Q;
  Q.push(src);
  dis[src] = 0, ins[src] = 1;
  pre[src] = -1;
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    ins[u] = 0;
    for (int e = head[u]; e != -1; e = nxt[e]) {
      int v = ver[e];
      if (!flow[e]) continue;
      if (dis[v] > dis[u] + cst[e]) {
        dis[v] = dis[u] + cst[e];
        pre[v] = e;
        if (!ins[v]) ins[v] = 1, Q.push(v);
      }
    }
  }
  return dis[dest] < inf;
}
int Dinic_flow() {
  int i, ret = 0, delta = inf;
  while (Dinic_spfa()) {
    for (int i = pre[dest]; i != -1; i = pre[ver[i ^ 1]])
      delta = min(delta, flow[i]);
    for (int i = pre[dest]; i != -1; i = pre[ver[i ^ 1]])
      flow[i] -= delta, flow[i ^ 1] += delta;
    ret += delta;
    tot_cost += dis[dest] * delta;
  }
  return ret;
}
int n;
int a[3333];
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  prepare(3 + 3 * n, 0, 1 + 3 * n);
  addedge(0, 2 + 3 * n, 4, 0);
  for (int i = 0; i < n; ++i) {
    addedge(2 + 3 * n, i * 3 + 1, 1, 0);
    addedge(i * 3 + 1, i * 3 + 2, 1, -1);
    addedge(i * 3 + 1, i * 3 + 3, inf, 0);
    addedge(i * 3 + 2, i * 3 + 3, 1, 0);
    addedge(i * 3 + 3, 1 + 3 * n, 1, 0);
  }
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (a[i] == a[j] + 1) {
        addedge(i * 3 + 3, j * 3 + 1, inf, 0);
        break;
      }
    }
    for (int j = i + 1; j < n; ++j) {
      if (a[i] == a[j] - 1) {
        addedge(i * 3 + 3, j * 3 + 1, inf, 0);
        break;
      }
    }
    for (int j = i + 1; j < n; ++j) {
      if (abs(a[i] - a[j]) % 7 == 0) {
        addedge(i * 3 + 3, j * 3 + 1, inf, 0);
        break;
      }
    }
  }
  int maxf = Dinic_flow();
  cout << -tot_cost << endl;
  return 0;
}