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;
inline int nxt() {
  int x;
  scanf("%d", &x);
  return x;
}
struct Edge {
  int from;
  int to;
  int cap;
  int cost;
  int flow;
};
struct Network {
  int n, s, t;
  vector<vector<int>> a;
  vector<Edge> edges;
  vector<int> phi;
  vector<int> pr;
  Network(int _n, int _s, int _t) : n(_n), s(_s), t(_t) { a.resize(n); }
  void add_edge(int from, int to, int cap, int cost) {
    a[from].push_back(edges.size());
    edges.push_back({from, to, cap, cost, 0});
    a[to].push_back(edges.size());
    edges.push_back({to, from, 0, -cost, 0});
  }
  void dijkstra() {
    vector<int> dist(n, INT_MAX / 2);
    dist[s] = 0;
    pr.assign(n, -1);
    set<pair<int, int>> S = {{0, s}};
    while (!S.empty()) {
      auto p = *S.begin();
      S.erase(S.begin());
      int v = p.second;
      for (auto ed_idx : a[v]) {
        auto ed = edges[ed_idx];
        if (ed.flow == ed.cap) {
          continue;
        }
        if (dist[ed.to] > dist[v] + ed.cost + phi[ed.from] - phi[ed.to]) {
          if (dist[ed.to] < INT_MAX / 3) {
            S.erase({dist[ed.to], ed.to});
          }
          dist[ed.to] = dist[v] + ed.cost + phi[ed.from] - phi[ed.to];
          pr[ed.to] = ed_idx;
          S.insert({dist[ed.to], ed.to});
        }
      }
    }
    phi.swap(dist);
  }
  int64_t mincostflow(int flow = INT_MAX) {
    int64_t cost = 0;
    phi.assign(n, 0);
    while (flow) {
      int cur_flow = flow;
      dijkstra();
      assert(pr[t] > -1);
      vector<int> ed_ids;
      int cur_v = t;
      while (cur_v != s) {
        ed_ids.push_back(pr[cur_v]);
        cur_flow = min(cur_flow, edges[pr[cur_v]].cap - edges[pr[cur_v]].flow);
        cur_v = edges[pr[cur_v]].from;
      }
      flow -= cur_flow;
      for (auto id : ed_ids) {
        cost += 1ll * edges[id].cost * cur_flow;
        edges[id].flow += cur_flow;
        edges[id ^ 1].flow -= cur_flow;
      }
    }
    return cost;
  }
  void show_flow() {
    for (int i = 0; i < n; ++i) {
      for (int id : a[i]) {
        auto ed = edges[id];
        if (ed.flow == 0) {
          continue;
        }
        cerr << ed.from << " -> " << ed.to << ": flow = " << ed.flow
             << " (cost = " << ed.cost << ")\n";
      }
    }
  }
};
int main() {
  int n = nxt();
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    a[i] = nxt();
  }
  Network net(2 * n + 2, 2 * n, 2 * n + 1);
  for (int i = 0; i < n; ++i) {
    net.add_edge(2 * n, 2 * i, 1, 0);
    net.add_edge(2 * i + 1, 2 * n + 1, 1, 0);
    net.add_edge(2 * i, 2 * i + 1, 1, -1);
    for (int j = i + 1; j < n; ++j) {
      if (a[j] == a[i] + 1) {
        net.add_edge(2 * i + 1, 2 * j, 1, 0);
        break;
      }
    }
    for (int j = i + 1; j < n; ++j) {
      if (a[j] == a[i] - 1) {
        net.add_edge(2 * i + 1, 2 * j, 1, 0);
        break;
      }
    }
    for (int j = i + 1; j < n; ++j) {
      if (a[i] == a[j]) {
        net.add_edge(2 * i, 2 * j, 1, 0);
        net.add_edge(2 * i + 1, 2 * j + 1, 1, 0);
        break;
      }
    }
    for (int j = i + 1; j < n; ++j) {
      if (a[j] % 7 == a[i] % 7) {
        net.add_edge(2 * i + 1, 2 * j + 1, 1, 0);
        net.add_edge(2 * i + 1, 2 * j, 1, 0);
        break;
      }
    }
  }
  cout << -net.mincostflow(2) << "\n";
  return 0;
}