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 pwr(long long base, long long p, long long mod) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = (ans * base) % mod;
    base = (base * base) % mod;
    p /= 2;
  }
  return ans;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
const int InfCost = 3002;
struct MinimumCostMaximumFlow {
  static const int InfCapacity = 10;
  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 bellmanFord = 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(), InfCost);
      if (bellmanFord || total.second == 0) {
        dist[s] = 0;
        for (int k = 0; k < n; k++) {
          bool update = false;
          for (int i = 0; i < n; i++)
            if (dist[i] != InfCost)
              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;
                if (dist[j] > d) {
                  dist[j] = d;
                  prev[j] = i;
                  prevEdge[j] = ei;
                  update = true;
                }
              }
          if (!update) break;
        }
      } 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 (d < dist[i]) d = dist[i];
            if (dist[j] > d) {
              dist[j] = d;
              prev[j] = i;
              prevEdge[j] = ei;
              q.push(make_pair(-d, j));
            }
          }
        }
      }
      if (dist[t] == InfCost) break;
      if (!bellmanFord)
        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 n, arr[3002];
int last1[100005], last2[10];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
  MinimumCostMaximumFlow mcmf;
  mcmf.init(1 + 1 + 2 * n + 1);
  int src = 0, sink = 1 + 1 + 2 * n;
  mcmf.add(src, 1, 4, 0);
  for (int i = 1; i <= n; i++) {
    mcmf.add(1 + i, 1 + n + i, 1, -1);
    mcmf.add(1, 1 + i, 1, 0);
    mcmf.add(1 + n + i, sink, 1, 0);
  }
  memset(last1, -1, sizeof(last1));
  memset(last2, -1, sizeof(last2));
  for (int i = n; i >= 1; i--) {
    if (last1[arr[i]] != -1) mcmf.add(1 + i, 1 + last1[arr[i]], n + 2, 0);
    if (last2[arr[i] % 7] != -1)
      mcmf.add(1 + i, 1 + last2[arr[i] % 7], n + 2, 0);
    if (last1[arr[i] - 1] != -1)
      mcmf.add(1 + n + i, 1 + last1[arr[i] - 1], 1, 0);
    if (last1[arr[i] + 1] != -1)
      mcmf.add(1 + n + i, 1 + last1[arr[i] + 1], 1, 0);
    if (last2[arr[i] % 7] != -1)
      mcmf.add(1 + n + i, 1 + last2[arr[i] % 7], 1, 0);
    last1[arr[i]] = i;
    last2[arr[i] % 7] = i;
  }
  cout << -mcmf.minimumCostMaximumFlow(src, sink, 4, true).first;
  return 0;
}