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;
struct flow {
  static const int N = 3000005, INF = 1e9;
  int n, s, t;
  struct edge {
    int v, w, f, c, nxt;
  } e[N];
  int head[N], cur[N], cnt;
  void addedge(int u, int v, int w, int f, int c) {
    cnt++;
    e[cnt].v = v, e[cnt].w = w, e[cnt].f = f, e[cnt].c = c;
    e[cnt].nxt = head[u];
    head[u] = cnt;
  }
  void add(int u, int v, int w, int c = 0) {
    addedge(u, v, w, w, c);
    addedge(v, u, w, 0, -c);
  }
  int h[N], dis[N], pre[N], pu[N];
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>>
      pq;
  int min_cost(int f) {
    int res = 0;
    for (int i = 1; i <= cnt; i += 2) e[i].f = e[i].w;
    for (int i = 2; i <= cnt; i += 2) e[i].f = 0;
    while (f > 0) {
      for (int i = 1; i <= n; i++) dis[i] = INF;
      dis[s] = 0;
      pq.emplace(0, s);
      while (!pq.empty()) {
        auto p = pq.top();
        pq.pop();
        int u = p.second;
        if (dis[u] < p.first) continue;
        for (int i = head[u]; i; i = e[i].nxt) {
          int v = e[i].v, c = e[i].c, f = e[i].f;
          if (f > 0 && dis[v] > dis[u] + c + h[u] - h[v]) {
            dis[v] = dis[u] + c + h[u] - h[v];
            pre[v] = i, pu[v] = u;
            pq.emplace(dis[v], v);
          }
        }
      }
      if (dis[t] == INF) return -1;
      for (int i = 1; i <= n; i++) h[i] += dis[i];
      int d = f;
      for (int u = t; u != s; u = pu[u]) d = min(d, e[pre[u]].f);
      f -= d;
      res += d * h[t];
      for (int u = t; u != s; u = pu[u]) {
        e[pre[u]].f -= d;
        e[(pre[u] - 1 ^ 1) + 1].f += d;
      }
    }
    return res;
  }
} g;
const int N = 3005;
int n, a[N];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  g.n = n * 2 + 2, g.s = n * 2 + 1, g.t = n * 2 + 2;
  for (int i = 1; i <= n; i++) {
    g.add(g.s, i * 2 - 1, 1, 0);
    g.add(i * 2, g.t, 1, 0);
    g.add(i * 2 - 1, i * 2, 1, -1);
    int s1 = 0, s2 = 0, s3 = 0;
    for (int j = i + 1; j <= n; j++) {
      if (s1 < 4 && a[i] % 7 == a[j] % 7) {
        s1++;
        g.add(i * 2, j * 2 - 1, 1, 0);
      }
      if (s2 < 4 && a[i] - a[j] == 1) {
        s2++;
        g.add(i * 2, j * 2 - 1, 1, 0);
      }
      if (s3 < 4 && a[i] - a[j] == -1) {
        s3++;
        g.add(i * 2, j * 2 - 1, 1, 0);
      }
    }
  }
  printf("%d\n", -g.min_cost(4));
  return 0;
}