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;
const int len = 6020;
int SIZE;
const int inf = (int)1e9;
int n;
vector<int> in;
vector<vector<int>> g;
int flow[len][len], cost[len][len], pot[len];
int get_p(int u, int v) { return cost[u][v] + pot[u] - pot[v]; }
int add_path(int from, int to) {
  vector<int> dist(SIZE, (int)1e9), prv(SIZE);
  vector<bool> check(SIZE, false);
  dist[from] = 0;
  check[from] = true;
  priority_queue<pair<int, int>> q;
  q.push(make_pair(0, from));
  while (!q.empty()) {
    auto tmp = q.top();
    tmp.first *= -1;
    q.pop();
    if (dist[tmp.second] != tmp.first) {
      continue;
    }
    check[tmp.second] = true;
    for (auto i : g[tmp.second]) {
      if (flow[tmp.second][i] > 0 &&
          dist[i] > dist[tmp.second] + get_p(tmp.second, i)) {
        dist[i] = dist[tmp.second] + get_p(tmp.second, i);
        prv[i] = tmp.second;
        q.push(make_pair(-dist[i], i));
      }
    }
  }
  for (int i = 0; i < SIZE; i++) {
    pot[i] += dist[i];
  }
  if (!check[to]) {
    return inf;
  }
  int ptr = to, cap = inf, sum = 0;
  while (ptr != from) {
    cap = min(cap, flow[prv[ptr]][ptr]);
    ptr = prv[ptr];
  }
  ptr = to;
  while (ptr != from) {
    flow[prv[ptr]][ptr] -= cap;
    flow[ptr][prv[ptr]] += cap;
    sum += cost[prv[ptr]][ptr];
    ptr = prv[ptr];
  }
  return sum;
}
int solve(int from, int to) {
  int sum = 0, tmp;
  while ((tmp = add_path(from, to)) != inf) {
    sum -= tmp;
  }
  return sum;
}
void add(int from, int to, int in_flow, int in_cost) {
  g[from].push_back(to);
  g[to].push_back(from);
  flow[from][to] = in_flow;
  cost[from][to] = in_cost;
  cost[to][from] = -in_cost;
}
vector<int> super_cnt[100001];
vector<int> cnt[7];
vector<int> top_sort;
bool check[len];
void dfs(int v, int prv) {
  check[v] = true;
  for (int i : g[v]) {
    if (!check[i]) {
      dfs(i, v);
    }
  }
  top_sort.push_back(v);
}
int main() {
  scanf("%d", &n);
  SIZE = 2 * n + 3;
  in.resize(SIZE);
  for (int i = 0; i < n; i++) {
    scanf("%d", &in[i]);
  }
  g.resize(SIZE, vector<int>());
  add(0, 1, 4, 0);
  for (int i = 0; i < n; i++) {
    add(2 * i + 3, 2 * i + 4, 1, -1);
    add(1, 2 * i + 3, 1, 0);
    add(2 * i + 4, 2, 1, 0);
    for (int j : cnt[in[i] % 7]) {
      add(2 * j + 4, 2 * i + 3, 1, 0);
    }
    for (int j : super_cnt[in[i] - 1]) {
      add(2 * j + 4, 2 * i + 3, 1, 0);
    }
    for (int j : super_cnt[in[i] + 1]) {
      add(2 * j + 4, 2 * i + 3, 1, 0);
    }
    cnt[in[i] % 7].push_back(i);
    super_cnt[in[i]].push_back(i);
  }
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < i; j++) {
      if (flow[j][i] && pot[j] + cost[j][i] < pot[i]) {
        pot[i] = pot[j] + cost[j][i];
      }
    }
  }
  dfs(0, -1);
  for (int i : top_sort) {
    for (int j : g[i]) {
      pot[j] += cost[i][j];
    }
  }
  cout << solve(0, 2);
  return 0;
}