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;
class Graph {
  struct Edge {
    int From, To, Capacity, Flow, Cost, ConstCost;
  };
  struct OrderedRib {
    int Source;
    Edge* Rib;
    bool Exist() const {
      return Source == Rib->From ? Rib->Capacity > Rib->Flow : Rib->Flow > 0;
    }
    int Destination() const {
      return Source == Rib->From ? Rib->To : Rib->From;
    }
    int Cost() const { return (Source == Rib->From ? 1 : -1) * Rib->Cost; }
    int Capacity() const {
      return Source == Rib->From ? Rib->Capacity - Rib->Flow : Rib->Flow;
    }
    void IncreaseFlow(int v) {
      Rib->Flow += (Source == Rib->From ? 1 : -1) * v;
    }
  };
  list<Edge> edges;
  vector<vector<OrderedRib> > adjacency_list;
  vector<int> BellmanFord() const {
    vector<int> distances(adjacency_list.size(), INF);
    distances[s] = 0;
    for (int i = 0; i < adjacency_list.size(); ++i) {
      for (const auto& e : edges) {
        if (distances[e.From] != INF)
          distances[e.To] = min(distances[e.To], distances[e.From] + e.Cost);
      }
    }
    return distances;
  }
  vector<int> ShortestPaths(vector<OrderedRib>& parents) {
    parents.resize(adjacency_list.size());
    vector<int> res(adjacency_list.size(), INF);
    using Key = pair<int, int>;
    set<Key> queue;
    queue.insert(Key(0, s));
    res[s] = 0;
    while (!queue.empty()) {
      auto next = *queue.begin();
      queue.erase(queue.begin());
      for (const auto& e : adjacency_list[next.second]) {
        int other = e.Destination();
        if (e.Exist() && (res[other] > next.first + e.Cost())) {
          res[other] = next.first + e.Cost();
          queue.insert(Key(res[other], other));
          parents[other] = e;
        }
      }
    }
    return res;
  }
  vector<int> ShortestPathsAlt(vector<OrderedRib>& parents) {
    size_t n = adjacency_list.size();
    parents.resize(n);
    vector<int> d(n, INF);
    d[s] = 0;
    vector<int> id(n);
    deque<int> q;
    q.push_back(s);
    while (!q.empty()) {
      int v = q.front();
      q.pop_front();
      id[v] = 1;
      for (const auto& e : adjacency_list[v]) {
        if (!e.Exist()) continue;
        int to = e.Destination(), len = e.Cost();
        if (d[to] > d[v] + len) {
          d[to] = d[v] + len;
          if (id[to] == 0)
            q.push_back(to);
          else if (id[to] == 1)
            q.push_front(to);
          parents[to] = e;
          id[to] = 1;
        }
      }
    }
    return d;
  }

 public:
  static const int INF;
  void ReduceCosts(const vector<int>& potentials) {
    for (auto& e : edges) {
      e.Cost += potentials[e.From] - potentials[e.To];
    }
  }

 private:
  void IncreaseFlow(vector<OrderedRib>& parents) {
    int current = t;
    int min_capacity = INF;
    while (current != s) {
      min_capacity = min(min_capacity, parents[current].Capacity());
      current = parents[current].Source;
    }
    min_capacity = min(residual_flow, min_capacity);
    residual_flow -= min_capacity;
    current = t;
    while (current != s) {
      parents[current].IncreaseFlow(min_capacity);
      cost += parents[current].Cost() * min_capacity;
      current = parents[current].Source;
    }
  }

 public:
  int cost = 0;
  int residual_flow;
  int s, t;
  Graph(size_t vertices) : adjacency_list(vertices) {}
  void AddRib(int from, int to, int cost, int capacity) {
    edges.push_back(Edge({from, to, capacity, 0, cost, cost}));
    adjacency_list[from].push_back(OrderedRib({from, &edges.back()}));
    adjacency_list[to].push_back(OrderedRib({to, &edges.back()}));
  }
  int MinCostFlow() {
    while (residual_flow) {
      vector<OrderedRib> parents;
      auto potentials = ShortestPathsAlt(parents);
      IncreaseFlow(parents);
    }
    return cost;
  }
};
const int Graph::INF = 1000000000;
int main() {
  vector<int> lst(100011, -1), lst2(7, -1);
  int n;
  cin >> n;
  Graph g(3 * n + 2);
  g.residual_flow = 4;
  g.s = 0;
  g.t = 1;
  vector<int> notes(n);
  using Value = pair<int, int>;
  vector<int> distances(3 * n + 2, 1000000000);
  distances[0] = 0;
  for (int i = 0; i < n; ++i) {
    cin >> notes[i];
  }
  for (int i = n - 1; i >= 0; --i) {
    g.AddRib(0, i + 2 * n + 2, 0, 1);
    g.AddRib(i + 2 * n + 2, i + 2, 0, 1);
    g.AddRib(i + 2, i + n + 2, -1, 1);
    g.AddRib(i + n + 2, 1, 0, 1);
    if (lst[notes[i] - 1] >= 0) {
      g.AddRib(i + n + 2, lst[notes[i] - 1] + 2, 0, 1);
    }
    if (lst[notes[i] + 1] >= 0) {
      g.AddRib(i + n + 2, lst[notes[i] + 1] + 2, 0, 1);
    }
    if (lst2[notes[i] % 7] >= 0) {
      g.AddRib(i + n + 2, lst2[notes[i] % 7] + 2 * n + 2, 0, 1);
    }
    if (lst[notes[i]] >= 0) {
      g.AddRib(i + 2, lst[notes[i]] + 2, 0, Graph::INF);
    }
    if (lst2[notes[i] % 7] >= 0) {
      g.AddRib(i + 2 * n + 2, lst2[notes[i] % 7] + 2 * n + 2, 0, Graph::INF);
    }
    lst2[notes[i] % 7] = lst[notes[i]] = i;
  }
  cout << -g.MinCostFlow();
  return 0;
}