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 MinCostFlow {
  struct edge {
    long long to, cap, cost, rev;
    edge() {}
    edge(long long a, long long b, long long c, long long d) {
      to = a, cap = b, cost = c, rev = d;
    }
  };
  int n;
  vector<vector<edge> > G;
  vector<long long> dist;
  vector<int> prevv, preve;
  vector<long long> h;
  MinCostFlow() {}
  MinCostFlow(int n) {
    this->n = n;
    G.resize(n + 1);
    dist.resize(n + 1);
    prevv.resize(n + 1);
    preve.resize(n + 1);
    h.resize(n + 1);
  }
  void BellmanFord(int s) {
    for (int i = 0; i <= n; i++) dist[i] = 1e18;
    dist[s] = 0, prevv[s] = -1;
    bool update = true;
    while (update) {
      update = false;
      for (int i = 0; i <= n; i++) {
        for (int j = 0; j < G[i].size(); j++) {
          if (G[i][j].cap == 0) continue;
          if (dist[G[i][j].to] > dist[i] + G[i][j].cost) {
            dist[G[i][j].to] = dist[i] + G[i][j].cost;
            prevv[G[i][j].to] = i;
            preve[G[i][j].to] = j;
            update = true;
          }
        }
      }
    }
  }
  void Dijkstra(int s) {
    for (int i = 0; i <= n; i++) dist[i] = 1e18;
    dist[s] = 0, prevv[s] = -1;
    priority_queue<pair<long long, long long>,
                   vector<pair<long long, long long> >,
                   greater<pair<long long, long long> > >
        Q;
    Q.push(make_pair(0, s));
    long long v, d;
    while (Q.size()) {
      d = Q.top().first;
      v = Q.top().second;
      Q.pop();
      if (dist[v] < d) continue;
      for (int i = 0; i < G[v].size(); i++) {
        if (G[v][i].cap == 0) continue;
        long long u = G[v][i].to, c = h[v] - h[u] + G[v][i].cost;
        if (dist[u] > d + c) {
          dist[u] = d + c;
          prevv[u] = v;
          preve[u] = i;
          Q.push(pair<long long, long long>(dist[u], u));
        }
      }
    }
  }
  void add_edge(int from, int to, long long cap, long long cost) {
    G[from].push_back(edge(to, cap, cost, G[to].size()));
    G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));
  }
  long long calc(int s, int t, long long f) {
    BellmanFord(s);
    for (int i = 0; i <= n; i++) h[i] = dist[i];
    long long ret = 0;
    while (f > 0) {
      Dijkstra(s);
      if (dist[t] >= 1e18) break;
      long long p = t, flow = f;
      while (prevv[p] != -1) {
        flow = min(flow, G[prevv[p]][preve[p]].cap);
        p = prevv[p];
      }
      p = t;
      while (prevv[p] != -1) {
        G[prevv[p]][preve[p]].cap -= flow;
        G[p][G[prevv[p]][preve[p]].rev].cap += flow;
        p = prevv[p];
      }
      f -= flow;
      ret += (dist[t] + h[t] - h[s]) * flow;
      for (int i = 0; i <= n; i++) h[i] += dist[i];
    }
    if (f > 0) return 1;
    return ret;
  }
};
long long n;
long long a[5005];
MinCostFlow mcf(20005);
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (long long(i) = (1); (i) <= (n); (i)++) cin >> a[i];
  long long S = 4 * n + 1, T = 4 * n + 2;
  for (long long(i) = (1); (i) <= (n); (i)++) {
    mcf.add_edge(S, 2 * n + i, 1, 0);
    mcf.add_edge(i, 2 * n + i, 1, 0);
    mcf.add_edge(n + i, 2 * n + i, 1, 0);
    mcf.add_edge(2 * n + i, 3 * n + i, 1, -1);
    mcf.add_edge(3 * n + i, T, 1, 0);
    for (long long(j) = (i + 1); (j) <= (n); (j)++) {
      if (a[j] == a[i]) {
        mcf.add_edge(i, j, 4, 0);
        break;
      }
    }
    for (long long(j) = (i + 1); (j) <= (n); (j)++) {
      if (a[j] % 7 == a[i] % 7) {
        mcf.add_edge(n + i, n + j, 4, 0);
        mcf.add_edge(3 * n + i, n + j, 4, 0);
        break;
      }
    }
    for (long long(j) = (i + 1); (j) <= (n); (j)++) {
      if (a[j] == a[i] + 1) {
        mcf.add_edge(3 * n + i, j, 1, 0);
        break;
      }
    }
    for (long long(j) = (i + 1); (j) <= (n); (j)++) {
      if (a[j] == a[i] - 1) {
        mcf.add_edge(3 * n + i, j, 1, 0);
        break;
      }
    }
  }
  cout << -mcf.calc(S, T, 2) << endl;
  return 0;
}