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>
#pragma GCC target("avx2,avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
constexpr char ln = '\n';
istream& operator>>(istream& is, __int128_t& x) {
  x = 0;
  string s;
  is >> s;
  int n = int(s.size()), it = 0;
  if (s[0] == '-') it++;
  for (; it < n; it++) x = (x * 10 + s[it] - '0');
  if (s[0] == '-') x = -x;
  return is;
}
ostream& operator<<(ostream& os, __int128_t x) {
  if (x == 0) return os << 0;
  if (x < 0) os << '-', x = -x;
  deque<int> deq;
  while (x) deq.emplace_front(x % 10), x /= 10;
  for (int e : deq) os << e;
  return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "{";
  for (int i = 0; i < int(v.size()); i++) {
    if (i) os << ", ";
    os << v[i];
  }
  return os << "}";
}
template <class Container>
inline int SZ(Container& v) {
  return int(v.size());
}
template <class T>
inline void UNIQUE(vector<T>& v) {
  v.erase(unique(v.begin(), v.end()), v.end());
}
template <class T1, class T2>
inline bool chmax(T1& a, T2 b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T1, class T2>
inline bool chmin(T1& a, T2 b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
inline int topbit(int x) { return x == 0 ? -1 : 31 - __builtin_clz(x); }
inline int topbit(long long x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
inline int botbit(int x) { return x == 0 ? 32 : __builtin_ctz(x); }
inline int botbit(long long x) { return x == 0 ? 64 : __builtin_ctzll(x); }
inline int popcount(int x) { return __builtin_popcount(x); }
inline int popcount(long long x) { return __builtin_popcountll(x); }
inline int kthbit(long long x, int k) { return (x >> k) & 1; }
inline constexpr long long TEN(int x) { return x == 0 ? 1 : TEN(x - 1) * 10; }
inline void print() { cout << "\n"; }
template <class T>
inline void print(const vector<T>& v) {
  for (int i = 0; i < int(v.size()); i++) {
    if (i) cout << " ";
    cout << v[i];
  }
  print();
}
template <class T, class... Args>
inline void print(const T& x, const Args&... args) {
  cout << x << " ";
  print(args...);
}
struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  };
} fast_ios_;
const int MAXN = 5000;
const int MAX = 1e5;
int A[MAXN + 2];
int mod[7];
int num[MAX + 2];
short nex[MAXN + 2][MAXN + 2][3];
short dp[MAXN + 2][MAXN + 2];
int main() {
  int N;
  cin >> N;
  for (int i = 1; i <= N; i++) cin >> A[i];
  for (int i = 0; i < (7); i++) mod[i] = N + 1;
  for (int i = 0; i < (MAX + 2); i++) num[i] = N + 1;
  for (int i = N; i > 0; i--) {
    int x = A[i] % 7;
    nex[i][0][0] = mod[x];
    nex[i][0][1] = num[A[i] + 1];
    nex[i][0][2] = num[A[i] - 1];
    for (int j = 1; j < i; j++) {
      int y = A[j] % 7;
      nex[i][j][0] = mod[y];
      nex[i][j][1] = num[A[j] + 1];
      nex[i][j][2] = num[A[j] - 1];
    }
    mod[x] = i;
    num[A[i]] = i;
  }
  for (int i = 1; i <= N; i++) dp[i][0] = 1;
  for (int i = 1; i <= N; i++) {
    for (int j = i + 1; j <= N; j++) chmax(dp[j][i], dp[i][0] + 1);
    for (int k = 0; k < (3); k++) {
      int n = nex[i][0][k];
      if (n == N + 1) continue;
      for (int j = 0; j < (i); j++) {
        chmax(dp[n][j], dp[i][j] + 1);
      }
    }
    for (int j = 1; j < i; j++) {
      for (int k = 0; k < (3); k++) {
        int n = nex[i][j][k];
        if (n == N + 1) continue;
        chmax(dp[n][i], dp[i][j] + 1);
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= N; i++) {
    for (int j = 0; j < (i); j++) chmax(ans, dp[i][j]);
  }
  cout << ans << ln;
}