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;
inline int read() {
  int x = 0;
  char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x;
}
int n, a[5005], cnt = 2, head[30005], ans = 0, dis[30005], rev[30005], p[7],
                tot, rt[100005];
bool inq[20005];
queue<int> que;
struct edge {
  int to, next, cap, c;
} e[100000];
inline void add_edge(int from, int to, int cap, int cost) {
  e[cnt].to = to;
  e[cnt].cap = cap;
  e[cnt].c = cost;
  e[cnt].next = head[from];
  head[from] = cnt++;
  e[cnt].to = from;
  e[cnt].cap = 0;
  e[cnt].c = -cost;
  e[cnt].next = head[to];
  head[to] = cnt++;
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    a[i] = read();
    add_edge(i << 1, i << 1 | 1, 1, -1);
    add_edge(0, i << 1, 1, 0);
    add_edge(i << 1 | 1, 1, 1, 0);
  }
  tot = n << 1 | 1;
  for (int i = 0; i < 7; ++i) p[i] = ++tot;
  for (int i = 1; i <= n; ++i) {
    add_edge(p[a[i] % 7], i << 1, 1, 0);
    add_edge(p[a[i] % 7], ++tot, INF, 0);
    p[a[i] % 7] = tot;
    add_edge(i << 1 | 1, p[a[i] % 7], 1, 0);
    if (rt[a[i] - 1]) add_edge(rt[a[i] - 1], i << 1, 1, 0);
    if (rt[a[i] + 1]) add_edge(rt[a[i] + 1], i << 1, 1, 0);
    if (!rt[a[i]]) {
      rt[a[i]] = ++tot;
      add_edge(i << 1 | 1, tot, 1, 0);
    } else {
      add_edge(i << 1 | 1, ++tot, 1, 0);
      add_edge(rt[a[i]], tot, INF, 0);
      rt[a[i]] = tot;
    }
  }
  for (int tim = 0; tim < 4; ++tim) {
    memset(dis, 63, sizeof(dis));
    memset(inq, false, sizeof(inq));
    while (!que.empty()) que.pop();
    que.push(0);
    dis[0] = 0;
    while (!que.empty()) {
      int x = que.front();
      que.pop();
      inq[x] = false;
      for (int i = head[x]; i; i = e[i].next) {
        if (!e[i].cap) continue;
        int y = e[i].to;
        if (dis[y] > dis[x] + e[i].c) {
          dis[y] = dis[x] + e[i].c;
          rev[y] = i;
          if (!inq[y]) {
            inq[y] = true;
            que.push(y);
          }
        }
      }
    }
    ans -= dis[1];
    int x = 1;
    while (x) {
      --e[rev[x]].cap;
      ++e[rev[x] ^ 1].cap;
      x = e[rev[x] ^ 1].to;
    }
  }
  printf("%d\n", ans);
  return 0;
}