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;
long long gcd(long long n1, long long n2) {
  if (n2 == 0) return n1;
  if (n1 % n2 == 0) return n2;
  return gcd(n2, n1 % n2);
}
long long powmod(long long base, long long exponent) {
  if (exponent < 0) exponent += 1000000007LL - 1;
  long long ans = 1;
  while (exponent) {
    if (exponent & 1) ans = (ans * base) % 1000000007LL;
    base = (base * base) % 1000000007LL;
    exponent /= 2;
  }
  return ans;
}
const int INF = 1e9;
struct MinimumCostMaximumFlow {
  static const int InfCapacity = INF;
  struct Edge {
    int to;
    int rev;
    int capacity;
    int cost;
  };
  vector<vector<Edge> > g;
  void init(int n) { g.assign(n, vector<Edge>()); }
  void add(int i, int j, int capacity = InfCapacity, int cost = int()) {
    Edge e, f;
    e.to = j, f.to = i;
    e.capacity = capacity, f.capacity = 0;
    e.cost = cost, f.cost = -cost;
    g[i].push_back(e);
    g[j].push_back(f);
    g[i].back().rev = (int)g[j].size() - 1;
    g[j].back().rev = (int)g[i].size() - 1;
  }
  void addB(int i, int j, int capacity = InfCapacity, int cost = int()) {
    add(i, j, capacity, cost);
    add(j, i, capacity, cost);
  }
  pair<int, int> minimumCostMaximumFlow(int s, int t, int f = InfCapacity,
                                        bool useSPFA = false) {
    int n = g.size();
    vector<int> dist(n);
    vector<int> prev(n);
    vector<int> prevEdge(n);
    pair<int, int> total = make_pair(0, 0);
    vector<int> potential(n);
    while (f > 0) {
      fill(dist.begin(), dist.end(), INF);
      if (useSPFA || total.second == 0) {
        deque<int> q;
        q.push_back(s);
        dist[s] = 0;
        vector<bool> inqueue(n);
        while (!q.empty()) {
          int i = q.front();
          q.pop_front();
          inqueue[i] = false;
          for (int ei = 0; ei < (int)g[i].size(); ei++) {
            const Edge &e = g[i][ei];
            int j = e.to;
            int d = dist[i] + e.cost;
            if (e.capacity > 0 && d < dist[j]) {
              if (!inqueue[j]) {
                inqueue[j] = true;
                q.push_back(j);
              }
              dist[j] = d;
              prev[j] = i;
              prevEdge[j] = ei;
            }
          }
        }
      } else {
        vector<bool> vis(n);
        priority_queue<pair<int, int> > q;
        q.push(make_pair(-0, s));
        dist[s] = 0;
        while (!q.empty()) {
          int i = q.top().second;
          q.pop();
          if (vis[i]) continue;
          vis[i] = true;
          for (int ei = 0; ei < (int)g[i].size(); ei++) {
            const Edge &e = g[i][ei];
            if (e.capacity <= 0) continue;
            int j = e.to;
            int d = dist[i] + e.cost + potential[i] - potential[j];
            if (dist[j] > d) {
              dist[j] = d;
              prev[j] = i;
              prevEdge[j] = ei;
              q.push(make_pair(-d, j));
            }
          }
        }
      }
      if (dist[t] == INF) break;
      if (!useSPFA)
        for (int i = 0; i < n; i++) potential[i] += dist[i];
      int d = f;
      int distt = 0;
      for (int v = t; v != s;) {
        int u = prev[v];
        const Edge &e = g[u][prevEdge[v]];
        d = min(d, e.capacity);
        distt += e.cost;
        v = u;
      }
      f -= d;
      total.first += d * distt;
      total.second += d;
      for (int v = t; v != s; v = prev[v]) {
        Edge &e = g[prev[v]][prevEdge[v]];
        e.capacity -= d;
        g[e.to][e.rev].capacity += d;
      }
    }
    return total;
  }
};
int arr[1000005];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  MinimumCostMaximumFlow pr;
  int n;
  cin >> n;
  pr.init(n + n + 5);
  for (int i = 1; i <= n; i++) cin >> arr[i];
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++) {
      if (arr[j] % 7 == arr[i] % 7) {
        pr.add(n + i, j, n + n, 0);
        pr.add(i, j, n + n, 0);
        break;
      }
    }
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++) {
      if (arr[j] - arr[i] == 1) {
        pr.add(n + i, j, n + n, 0);
        break;
      }
    }
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++) {
      if (arr[j] - arr[i] == -1) {
        pr.add(n + i, j, n + n, 0);
        break;
      }
    }
  for (int i = 1; i <= n; i++) {
    pr.add(0, i, 1, 0);
    pr.add(i, n + i, 1, -1);
    pr.add(n + i, n + n + 1, 1, 0);
  }
  pair<int, int> res = pr.minimumCostMaximumFlow(0, n + n + 1, 2, false);
  res.first *= -1;
  cout << res.first << '\n';
}