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>
const long long INF = std::numeric_limits<long long>::max();
struct edge {
  int u, v;
  long long cost, cap, flow;
  edge(int u, int v, long long cost, long long cap, long long flow)
      : u(u), v(v), cost(cost), cap(cap), flow(flow) {}
};
struct flow_network {
  int n, s, t, *par, *in_queue, *num_vis;
  long long *dist, *pot;
  std::vector<edge> edges;
  std::vector<int> *adj;
  flow_network(int n, int s, int t) : n(n), s(s), t(t) {
    adj = new std::vector<int>[n];
    par = new int[n];
    in_queue = new int[n];
    num_vis = new int[n];
    dist = new long long[n];
    pot = new long long[n];
    for (int u = 0; u < n; ++u) pot[u] = 0;
  }
  void add_edge(int u, int v, long long cap, long long cost) {
    adj[u].push_back(edges.size());
    edges.push_back(edge(u, v, cost, cap, 0LL));
    adj[v].push_back(edges.size());
    edges.push_back(edge(v, u, -cost, 0LL, 0LL));
  }
  long long res(edge &e) { return e.cap - e.flow; }
  void bellman_ford() {
    for (int u = 0; u < n; ++u) pot[u] = INF;
    pot[s] = 0;
    for (int it = 0; it < n - 1; ++it)
      for (auto e : edges)
        if (res(e) > 0) pot[e.v] = std::min(pot[e.v], pot[e.u] + e.cost);
  }
  bool spfa() {
    std::queue<int> q;
    q.push(s);
    while (not q.empty()) {
      int u = q.front();
      q.pop();
      in_queue[u] = 0;
      if (++num_vis[u] >= n) {
        dist[u] = -INF;
        continue;
      }
      for (int i : adj[u]) {
        edge e = edges[i];
        if (res(e) <= 0) continue;
        long long nd = dist[u] + e.cost + pot[u] - pot[e.v];
        if (dist[e.v] > nd) {
          dist[e.v] = nd;
          par[e.v] = i;
          if (not in_queue[e.v]) {
            q.push(e.v);
            in_queue[e.v] = 1;
          }
        }
      }
    }
    return dist[t] != INF;
  }
  bool aug_path() {
    for (int u = 0; u < n; ++u) {
      par[u] = -1;
      in_queue[u] = 0;
      num_vis[u] = 0;
      dist[u] = INF;
    }
    dist[s] = 0;
    in_queue[s] = 1;
    return spfa();
  }
  std::pair<long long, long long> calc_max_flow(bool do_bellman_ford = false) {
    long long total_cost = 0, total_flow = 0;
    if (do_bellman_ford) bellman_ford();
    while (aug_path()) {
      long long f = INF;
      for (int i = par[t]; i != -1; i = par[edges[i].u])
        f = std::min(f, res(edges[i]));
      for (int i = par[t]; i != -1; i = par[edges[i].u]) {
        edges[i].flow += f;
        edges[i ^ 1].flow -= f;
      }
      total_cost += f * (dist[t] + pot[t] - pot[s]);
      total_flow += f;
      for (int u = 0; u < n; ++u)
        if (par[u] != -1) pot[u] += dist[u];
    }
    return {total_cost, total_flow};
  }
};
int N, A[100001], LIM = 10;
int in_node(int u) { return u; }
int out_node(int u) { return u + N; }
int main() {
  std::cin >> N;
  for (int i = 0; i < N; ++i) std::cin >> A[i];
  int ss = 2 * N;
  int s = 2 * N + 1;
  int t = 2 * N + 2;
  flow_network g(2 * N + 3, ss, t);
  g.add_edge(ss, s, 4, 0);
  for (int i = 0; i < N; ++i) {
    g.add_edge(s, in_node(i), 1, 0);
    g.add_edge(in_node(i), out_node(i), 1, -1);
    g.add_edge(out_node(i), t, 1, 0);
    int a = 0, b = 0, c = 0;
    for (int j = i + 1; j < N; ++j) {
      if (A[i] - A[j] == -1 and a < LIM) {
        g.add_edge(out_node(i), in_node(j), 1, 0);
        a++;
      } else if (A[i] - A[j] == 1 and b < LIM) {
        g.add_edge(out_node(i), in_node(j), 1, 0);
        b++;
      } else if ((A[i] - A[j]) % 7 == 0 and c < LIM) {
        g.add_edge(out_node(i), in_node(j), 1, 0);
        c++;
      }
    }
  }
  std::cout << -g.calc_max_flow().first << "\n";
  return 0;
}