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 SSP {
  int n, source, sink;
  vector<vector<int> > adj;
  struct edge {
    int u, flow, cap, cost, origcost;
  };
  vector<edge> edges;
  SSP(int n, int source, int sink) : n(n), source(source), sink(sink), adj(n) {}
  int add_edge(int a, int b, int cap, int cost) {
    int result = edges.size();
    adj[a].push_back(edges.size());
    edges.push_back({b, 0, cap, cost, cost});
    adj[b].push_back(edges.size());
    edges.push_back({a, 0, 0, -cost, -cost});
    return result;
  }
  pair<int, int> djk() {
    struct state_t {
      int dist, prev, maxf;
    };
    queue<int> q;
    vector<state_t> states(n, {INT_MAX / 2, -1, 0});
    states[source] = {0, -2, INT_MAX};
    vector<int> inqueue(n, 0);
    inqueue[source] = 1;
    q.push(source);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      inqueue[v] = 0;
      for (int edid : adj[v]) {
        edge& ed = edges[edid];
        if (ed.flow < ed.cap && states[ed.u].dist > states[v].dist + ed.cost) {
          states[ed.u].dist = states[v].dist + ed.cost;
          states[ed.u].prev = edid;
          states[ed.u].maxf = min(states[v].maxf, ed.cap - ed.flow);
          if (!inqueue[ed.u]) q.push(ed.u), inqueue[ed.u] = 1;
        }
      }
    }
    int lastid = states[sink].prev, extraflow = states[sink].maxf, atcost = 0;
    if (lastid == -1) return {0, 0};
    for (int id = lastid; id != -2; id = states[edges[id ^ 1].u].prev) {
      edges[id].flow += extraflow;
      edges[id ^ 1].flow -= extraflow;
      atcost += edges[id].origcost;
    }
    for (int id = 0; id < (int)edges.size(); id++) {
      int v = edges[id ^ 1].u, u = edges[id].u;
      if (states[v].prev != -1 && states[u].prev != -1)
        edges[id].cost += states[v].dist - states[u].dist;
    }
    return {extraflow, atcost};
  }
  pair<int, int> mfmc() {
    int flow = 0, cost = 0;
    if (any_of(edges.begin(), edges.end(),
               [](const edge& ed) { return ed.flow > 0 && ed.cost < 0; }))
      bellamanford();
    int extraflow, atcost;
    while (tie(extraflow, atcost) = djk(), extraflow > 0)
      flow += extraflow, cost += extraflow * atcost;
    return {flow, cost};
  }
  void bellamanford() {
    vector<int> dist(n, INT_MAX / 2);
    dist[source] = 0;
    for (int rep = 0; rep < n; rep++) {
      bool changed = false;
      for (int id = 0; id < (int)edges.size(); id++) {
        int v = edges[id ^ 1].u, u = edges[id].u;
        if (edges[id].flow < edges[id].cap && dist[v] != INT_MAX / 2 &&
            dist[u] > dist[v] + edges[id].cost) {
          dist[u] = dist[v] + edges[id].cost;
          changed = true;
          assert(rep < n - 1);
        }
      }
      if (!changed) break;
    }
    for (int id = 0; id < (int)edges.size(); id++) {
      int v = edges[id ^ 1].u, u = edges[id].u;
      if (dist[v] < INT_MAX / 2 && dist[u] < INT_MAX / 2)
        edges[id].cost += dist[v] - dist[u];
    }
  }
};
const int maxn = 3030;
const int magic = ((int)log2(maxn));
int in[maxn], out[maxn], arr[maxn];
int cnt = 0;
int get_node() {
  cnt++;
  return cnt - 1;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int e = 0; e < n; e++) scanf("%d", arr + e);
  int source = get_node();
  int sink = get_node();
  int ssink = get_node();
  for (int e = 0; e < n; e++) in[e] = get_node();
  for (int e = 0; e < n; e++) out[e] = get_node();
  SSP solver(cnt, source, ssink);
  for (int e = 0; e < n; e++) solver.add_edge(in[e], out[e], 1, -1);
  for (int e = 0; e < n; e++) solver.add_edge(source, in[e], 1, 0);
  for (int e = 0; e < n; e++) solver.add_edge(out[e], sink, 1, 0);
  for (int e = 0; e < n; e++) {
    int qtd_by_1 = 0;
    int qtd_by_7 = 0;
    for (int f = e + 1; f < n; f++) {
      if (abs(arr[e] - arr[f]) == 1 && qtd_by_1 < 2 * magic) {
        solver.add_edge(out[e], in[f], 1, 0);
        qtd_by_1++;
      } else if ((arr[e] % 7) == (arr[f] % 7) && qtd_by_7 < magic) {
        solver.add_edge(out[e], in[f], 1, 0);
        qtd_by_7++;
      }
    }
  }
  solver.add_edge(sink, ssink, 4, 0);
  pair<int, int> ans = solver.mfmc();
  printf("%d\n", -ans.second);
  return 0;
}