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 NMAX = 6010;
const int MMAX = 15 * NMAX;
namespace mcmf {
int n, m, s, t;
vector<int> graph[NMAX];
const int INF = 1e9 + 15;
int potentials[NMAX];
bool vis[NMAX];
int dist[NMAX];
int father[NMAX];
priority_queue<pair<int, int> > _queue;
void init(int _n, int _s, int _t) {
  m = 0;
  n = _n, s = _s, t = _t;
  for (int i = 1; i <= n; i++) graph[i].clear();
}
struct Edge {
  int from, to;
  int flow, cap, cost;
  Edge(int _from = 0, int _to = 0, int _flow = 0, int _cap = 0, int _cost = 0)
      : from(_from), to(_to), flow(_flow), cap(_cap), cost(_cost) {}
  inline int other(int node) { return from ^ to ^ node; }
};
Edge edges[2 * MMAX];
void addEdge(int from, int to, int cap, int cost) {
  edges[m++] = Edge(from, to, 0, cap, cost);
  edges[m++] = Edge(to, from, 0, 0, -cost);
  graph[from].push_back(m - 2);
  graph[to].push_back(m - 1);
}
int BellmanDP(int node) {
  if (vis[node]) return potentials[node];
  if (node == s) {
    potentials[s] = 0;
    return 0;
  }
  vis[node] = true;
  potentials[node] = INF;
  for (auto edg : graph[node])
    if (edges[edg ^ 1].flow < edges[edg ^ 1].cap)
      potentials[node] =
          min(potentials[node],
              BellmanDP(edges[edg ^ 1].other(node)) + edges[edg ^ 1].cost);
  return potentials[node];
}
bool Dijkstra() {
  memset(vis, 0, (n + 1) * sizeof(bool));
  for (int i = 1; i <= n; ++i) dist[i] = INF;
  dist[s] = 0;
  _queue.push(make_pair(0, s));
  int node;
  while (!_queue.empty()) {
    node = _queue.top().second;
    _queue.pop();
    if (vis[node]) continue;
    vis[node] = true;
    for (auto edge : graph[node]) {
      int other = edges[edge].other(node);
      int cost = edges[edge].cost + potentials[node] - potentials[other];
      if (edges[edge].flow < edges[edge].cap &&
          dist[node] + cost < dist[other]) {
        dist[other] = dist[node] + cost;
        father[other] = edge;
        _queue.push(make_pair(-dist[other], other));
      }
    }
  }
  for (int i = 1; i <= n; ++i) dist[i] += (potentials[i] - potentials[s]);
  return vis[t];
}
pair<int, int> JohnsonDinic() {
  memset(potentials, 0, (n + 1) * sizeof(int));
  BellmanDP(t);
  int flow = 0, cost = 0;
  while (Dijkstra()) {
    int node = t;
    int minimum = INF;
    int sum = 0;
    while (node != s) {
      minimum =
          min(minimum, edges[father[node]].cap - edges[father[node]].flow);
      sum += edges[father[node]].cost;
      node = edges[father[node]].other(node);
    }
    node = t;
    while (node != s) {
      edges[father[node]].flow += minimum;
      edges[father[node] ^ 1].flow -= minimum;
      node = edges[father[node]].other(node);
    }
    flow += minimum;
    cost += minimum * sum;
    memcpy(potentials, dist, (n + 1) * sizeof(int));
  }
  return make_pair(flow, cost);
}
inline pair<int, int> computeFlow() { return JohnsonDinic(); }
}  // namespace mcmf
int N;
int a[NMAX];
const int VALMAX = 100000 + 5;
vector<int> freq[VALMAX];
vector<int> freq7[7];
int main() {
  cin >> N;
  for (int i = 1; i <= N; ++i) cin >> a[i];
  int src = 2 * N + 1, snk = 2 * N + 3;
  mcmf::init(snk, src, snk);
  mcmf::addEdge(2 * N + 2, 2 * N + 3, 4, 0);
  for (int i = 1; i <= N; ++i) {
    mcmf::addEdge(2 * N + 1, i, 1, -1);
    mcmf::addEdge(i, N + i, 1, 0);
    mcmf::addEdge(N + i, 2 * N + 2, 1, 0);
  }
  for (int i = N; i; --i) {
    for (int j = 0; j < freq[a[i] + 1].size() && j < 4; ++j)
      mcmf::addEdge(N + i, freq[a[i] + 1][freq[a[i] + 1].size() - j - 1], 1,
                    -1);
    for (int j = 0; j < freq[a[i] - 1].size() && j < 4; ++j)
      mcmf::addEdge(N + i, freq[a[i] - 1][freq[a[i] - 1].size() - j - 1], 1,
                    -1);
    for (int j = 0; j < freq7[a[i] % 7].size() && j < 4; ++j)
      mcmf::addEdge(N + i, freq7[a[i] % 7][freq7[a[i] % 7].size() - j - 1], 1,
                    -1);
    freq[a[i]].push_back(i);
    freq7[a[i] % 7].push_back(i);
  }
  auto ans = mcmf::computeFlow();
  cout << -ans.second << '\n';
  return 0;
}