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 int mod = 1000000007;
const int gmod = 3;
const int inf = 1039074182;
const double eps = 1e-9;
const long long llinf = 2LL * inf * inf;
template <typename T1, typename T2>
inline void chmin(T1 &x, T2 b) {
  if (b < x) x = b;
}
template <typename T1, typename T2>
inline void chmax(T1 &x, T2 b) {
  if (b > x) x = b;
}
inline void chadd(int &x, int b) {
  x += b - mod;
  x += (x >> 31 & mod);
}
template <typename T1, typename T2>
inline void chadd(T1 &x, T2 b) {
  x += b;
  if (x >= mod) x -= mod;
}
template <typename T1, typename T2>
inline void chmul(T1 &x, T2 b) {
  x = 1LL * x * b % mod;
}
template <typename T1, typename T2>
inline void chmod(T1 &x, T2 b) {
  x %= b, x += b;
  if (x >= b) x -= b;
}
template <typename T>
inline T mabs(T x) {
  return (x < 0 ? -x : x);
}
using namespace std;
using namespace std;
template <typename T>
ostream &operator<<(ostream &cout, vector<T> vec) {
  cout << "{";
  for (int i = 0; i < (int)vec.size(); i++) {
    cout << vec[i];
    if (i != (int)vec.size() - 1) cout << ',';
  }
  cout << "}";
  return cout;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &cout, pair<T1, T2> p) {
  cout << "(" << p.first << ',' << p.second << ")";
  return cout;
}
template <typename T, typename T2>
ostream &operator<<(ostream &cout, set<T, T2> s) {
  vector<T> t;
  for (auto x : s) t.push_back(x);
  cout << t;
  return cout;
}
template <typename T, typename T2>
ostream &operator<<(ostream &cout, multiset<T, T2> s) {
  vector<T> t;
  for (auto x : s) t.push_back(x);
  cout << t;
  return cout;
}
template <typename T>
ostream &operator<<(ostream &cout, queue<T> q) {
  vector<T> t;
  while (q.size()) {
    t.push_back(q.front());
    q.pop();
  }
  cout << t;
  return cout;
}
template <typename T1, typename T2, typename T3>
ostream &operator<<(ostream &cout, map<T1, T2, T3> m) {
  for (auto &x : m) {
    cout << "Key: " << x.first << ' ' << "Value: " << x.second << endl;
  }
  return cout;
}
template <typename T1, typename T2>
void operator+=(pair<T1, T2> &x, const pair<T1, T2> y) {
  x.first += y.first;
  x.second += y.second;
}
template <typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2> &x, const pair<T1, T2> &y) {
  return make_pair(x.first + y.first, x.second + y.second);
}
template <typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2> &x, const pair<T1, T2> &y) {
  return make_pair(x.first - y.first, x.second - y.second);
}
template <typename T1, typename T2>
pair<T1, T2> operator-(pair<T1, T2> x) {
  return make_pair(-x.first, -x.second);
}
template <typename T>
vector<vector<T>> operator~(vector<vector<T>> vec) {
  vector<vector<T>> v;
  int n = vec.size(), m = vec[0].size();
  v.resize(m);
  for (int i = 0; i < m; i++) {
    v[i].resize(n);
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      v[i][j] = vec[j][i];
    }
  }
  return v;
}
void print0x(int x) {
  std::vector<int> vec;
  while (x) {
    vec.push_back(x & 1);
    x >>= 1;
  }
  std::reverse(vec.begin(), vec.end());
  for (int i = 0; i < (int)vec.size(); i++) {
    std::cout << vec[i];
  }
  std::cout << ' ';
}
template <typename T>
void print0x(T x, int len) {
  std::vector<int> vec;
  while (x) {
    vec.push_back(x & 1);
    x >>= 1;
  }
  reverse(vec.begin(), vec.end());
  for (int i = (int)vec.size(); i < len; i++) {
    putchar('0');
  }
  for (size_t i = 0; i < vec.size(); i++) {
    std::cout << vec[i];
  }
  std::cout << ' ';
}
vector<string> vec_splitter(string s) {
  s += ',';
  vector<string> res;
  while (!s.empty()) {
    res.push_back(s.substr(0, s.find(',')));
    s = s.substr(s.find(',') + 1);
  }
  return res;
}
void debug_out(vector<string> __attribute__((unused)) args,
               __attribute__((unused)) int idx,
               __attribute__((unused)) int LINE_NUM) {
  cerr << endl;
}
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
  if (idx > 0)
    cerr << ", ";
  else
    cerr << "Line(" << LINE_NUM << ") ";
  stringstream ss;
  ss << H;
  cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
struct NetworkWithCost {
  struct Edge {
    int vertex;
    int flow;
    int cost;
    int inv;
  };
  vector<Edge> *edges;
  inline void addEdge(int x, int y, int limit, int cost) {
    Edge edge;
    edge.cost = cost;
    edge.flow = limit;
    edge.vertex = y;
    edge.inv = (int)edges[y].size();
    edges[x].push_back(edge);
    edge.vertex = x;
    edge.flow = 0;
    edge.cost = -cost;
    edge.inv = (int)edges[x].size() - 1;
    edges[y].push_back(edge);
  }
  int src, dst;
  int n;
  void init(int _n) {
    n = _n;
    edges = new vector<Edge>[n];
    src = dst = -1;
  }
  void feedsd(int _src, int _dst) {
    src = _src;
    dst = _dst;
  }
  void clear() {
    for (int i = 0; i < n; i++) {
      edges[i].clear();
    }
    src = dst = -1;
  }
};
namespace MCMFSpace {
void operator+=(pair<int, int> &a, const pair<int, int> &b) {
  a.first += b.first;
  a.second += b.second;
}
}  // namespace MCMFSpace
struct MCMF {
  const int DistInf = 1039074182;
  NetworkWithCost g;
  int *dist;
  bool *visit;
  int *cur;
  queue<int> que;
  inline void init(NetworkWithCost &_g) {
    g = _g;
    dist = new int[g.n + 5];
    visit = new bool[g.n + 5];
    cur = new int[g.n + 5];
  }
  bool bellmanford() {
    for (int i = 0; i < g.n; i++) {
      dist[i] = inf;
    }
    dist[g.src] = 0;
    int changeCommitted;
    for (int T = 0; T < g.n; T++) {
      changeCommitted = 0;
      for (int i = 0; i < g.n; i++) {
        if (dist[i] == inf) continue;
        for (auto &e : g.edges[i]) {
          if (e.flow == 0) continue;
          if (dist[e.vertex] > dist[i] + e.cost) {
            dist[e.vertex] = dist[i] + e.cost;
            changeCommitted = true;
          }
        }
      }
      if (!changeCommitted) break;
    }
    return (dist[g.dst] < inf);
  }
  bool dijkstra() {
    for (int i = 0; i < g.n; i++) {
      dist[i] = -1;
    }
    dist[g.src] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>
        pq;
    pq.push(make_pair(0, 0));
    while (pq.size()) {
      int x = pq.top().second;
      int cost = pq.top().first;
      pq.pop();
      if (dist[x] != cost) continue;
      for (auto &e : g.edges[x]) {
        if (e.flow == 0) continue;
        if (dist[e.vertex] > cost + e.cost || dist[e.vertex] == -1) {
          dist[e.vertex] = cost + e.cost;
          pq.push(make_pair(dist[e.vertex], e.vertex));
        }
      }
    }
    return (dist[g.dst] != -1);
  }
  pair<int, int> dfs(int x, int flow) {
    if (x == g.dst) return make_pair(flow, 0);
    visit[x] = 1;
    pair<int, int> res = {0, 0};
    for (int &i = cur[x]; i < (int)g.edges[x].size(); i++) {
      int u = g.edges[x][i].vertex;
      int c = g.edges[x][i].cost;
      if (visit[u]) continue;
      if (dist[u] != dist[x] + c) continue;
      if (g.edges[x][i].flow == 0) continue;
      pair<int, int> f = dfs(u, min(flow, g.edges[x][i].flow));
      flow -= f.first;
      res += f;
      res.second += g.edges[x][i].cost * f.first;
      g.edges[x][i].flow -= f.first;
      g.edges[u][g.edges[x][i].inv].flow += f.first;
      if (flow == 0) break;
    }
    visit[x] = 0;
    return res;
  }
  pair<int, int> run() {
    pair<int, int> x = make_pair(0, 0);
    for (int i = 0; i < g.n; i++) {
      visit[i] = 0;
    }
    while (bellmanford()) {
      for (int i = 0; i < g.n; i++) {
        assert(visit[i] == 0);
      }
      for (int i = 0; i < g.n; i++) {
        cur[i] = 0;
      }
      pair<int, int> f = dfs(g.src, inf);
      x += f;
    }
    return x;
  }
};
using namespace std;
NetworkWithCost g;
MCMF d;
int n;
int a[3005];
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int nodes = n + n + 3;
  g.init(nodes);
  int src = nodes - 2, dst = nodes - 1;
  int lim = nodes - 3;
  g.feedsd(src, dst);
  for (int i = 0; i < n; i++) {
    int f1 = 0, f2 = 0, f3 = 0;
    for (int j = i + 1; j < n; j++) {
      if (f1 <= 4 && a[j] - 1 == a[i]) f1++, g.addEdge(i, j + n, 1, 0);
      if (f2 <= 4 && a[j] % 7 == a[i] % 7) f2++, g.addEdge(i, j + n, 1, 0);
      if (f3 <= 4 && a[j] + 1 == a[i]) f3++, g.addEdge(i, j + n, 1, 0);
    }
    g.addEdge(i + n, i, 1, -1);
  }
  g.addEdge(src, lim, 4, 0);
  for (int i = 0; i < n; i++) {
    g.addEdge(lim, i + n, 1, 0);
    g.addEdge(i, dst, 1, 0);
  }
  d.init(g);
  pair<int, int> f = d.run();
  cout << -f.second << endl;
  return 0;
}