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 edge {
  int x, y, nxt;
  long long cap, cost;
  edge() {}
  edge(int e_x, int e_y, long long e_cap, long long e_cost, int e_nxt) {
    x = e_x;
    y = e_y;
    cap = e_cap;
    cost = e_cost;
    nxt = e_nxt;
  }
};
edge edges[9000005];
int n, m, edge_cnt;
int last_pos[6010], head[6010];
int source, sink;
long long dist[6010];
int prv[6010];
bool vis[6010], mark[100005];
long long a[6010];
void add_edge(int x, int y, long long cap, long long cost) {
  if (head[x] == -1) head[x] = edge_cnt;
  if (last_pos[x] != -1) edges[last_pos[x]].nxt = edge_cnt;
  edges[edge_cnt] = edge(x, y, cap, cost, -1);
  last_pos[x] = edge_cnt;
  edge_cnt++;
  if (head[y] == -1) head[y] = edge_cnt;
  if (last_pos[y] != -1) edges[last_pos[y]].nxt = edge_cnt;
  edges[edge_cnt] = edge(y, x, 0, -cost, -1);
  last_pos[y] = edge_cnt;
  edge_cnt++;
  return;
}
bool SPFA() {
  for (int i = source; i <= sink; i++) {
    dist[i] = 999999999999999;
    vis[i] = false;
    prv[i] = -1;
  }
  queue<int> q;
  q.push(source);
  vis[source] = true;
  dist[source] = 0;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    vis[x] = false;
    for (int i = head[x]; i != -1; i = edges[i].nxt) {
      int y = edges[i].y;
      long long w = dist[x] + edges[i].cost;
      if (edges[i].cap && dist[y] > w) {
        dist[y] = w;
        prv[y] = i;
        if (!vis[y]) {
          q.push(y);
          vis[y] = true;
        }
      }
    }
  }
  return (dist[sink] <= 0);
}
void MCMF() {
  long long flow, mx_flow = 0, min_cost = 0;
  while (SPFA()) {
    flow = 999999999999999;
    for (int i = prv[sink]; i != -1; i = prv[edges[i].x])
      flow = min(flow, edges[i].cap);
    mx_flow += flow;
    for (int i = prv[sink]; i != -1; i = prv[edges[i].x]) {
      edges[i].cap -= flow;
      edges[i ^ 1].cap += flow;
      min_cost += (edges[i].cost * flow);
    }
  }
  printf("%lld\n", (-1) * min_cost);
  return;
}
void print_edges() {
  for (int i = 1; i <= n; i++) cout << i << " " << head[i] << endl;
  for (int i = 0; i < edge_cnt; i++)
    cout << edges[i].x << " " << edges[i].y << " " << edges[i].cap << " "
         << edges[i].cost << " " << edges[i].nxt << endl;
  return;
}
int main() {
  edge_cnt = 0;
  memset(head, -1, sizeof(head));
  memset(last_pos, -1, sizeof(last_pos));
  scanf("%d", &n);
  source = 0;
  sink = (n + 1) + n + 2;
  add_edge(source, 1, 4, 0);
  add_edge(((n + 1) + n + 1), sink, 4, 0);
  for (int i = 2; i <= (n + 1); i++) {
    scanf("%lld", &a[i]);
    add_edge(i, (n + i), 1, -1);
    add_edge(1, i, 1, 0);
    add_edge((n + i), ((n + 1) + n + 1), 1, 0);
  }
  for (int i = 2; i <= (n + 1); i++) {
    int c = 0;
    for (int j = (i + 1); (j <= (n + 1) & c <= 4); j++) {
      if ((a[i] - a[j]) == -1) {
        c++;
        add_edge((n + i), j, 1, 0);
      }
    }
  }
  for (int i = 2; i <= (n + 1); i++) {
    int c = 0;
    for (int j = (i + 1); (j <= (n + 1) & c <= 4); j++) {
      if ((a[i] - a[j]) == 1) {
        c++;
        add_edge((n + i), j, 1, 0);
      }
    }
  }
  for (int i = 2; i <= (n + 1); i++) {
    int c = 0;
    for (int j = (i + 1); (j <= (n + 1) & c <= 4); j++) {
      if (abs(a[i] - a[j]) % 7 == 0) {
        c++;
        add_edge((n + i), j, 1, 0);
      }
    }
  }
  MCMF();
  return 0;
}