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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.util.Collection;
import java.util.Random;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jialin Ouyang (Jialin.Ouyang@gmail.com)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    QuickScanner in = new QuickScanner(inputStream);
    QuickWriter out = new QuickWriter(outputStream);
    TaskD solver = new TaskD();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskD {
    int n;
    int[] a;
    int[][] dp;
    int[][] jump;
    int[] a7;
    int[] aDis;
    IntArrayList dis;
    IntArrayList[] storageDis;
    IntArrayList[] storage7;

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      n = in.nextInt();
      a = in.nextInt(n);
      initDis();
      initStorage();
      out.println(calc());
//    initSingleJump();
//    singleJump = new int[3][n];
//    for (int mode = 0; mode < 3; ++mode) {
//      initSingleJump(singleJump[mode], checkers[mode]);
//    }
//    jump = new int[3][n];
//    out.println(calc());
    }

    int calc() {
//System.out.printf("aDis:%s\n", IntArrayUtils.toString(aDis));
      dp = new int[n + 1][n + 1];
      jump = new int[3][n];
      Arrays.fill(dp[0], 1, n + 1, 1);
      for (int i = n - 1; i >= 0; --i) {
        Arrays.fill(dp[i + 1], -1);
        add(i);
      }
      for (int end = 0; end < n; ++end) {
        remove(end);
        for (int mode = 0; mode < 3; ++mode)
          for (int start = 0; start <= end; ++start) {
            jump[mode][start] = calc(mode, start);
//if (jump[mode][start] >= 0) {
//  print();
//  System.out.printf("%s: %d(%d) -> %d -> %d(%d)\n", mode == 0 ? "ADD" : mode == 1 ? "DEC" : "SAME", start, a[start], end, jump[mode][start], a[jump[mode][start]]);
//}
          }
        for (int nxtEnd = end + 1; nxtEnd < n; ++nxtEnd) {
          update(end + 1, nxtEnd + 1, dp[0][end + 1] + 1);
        }
        for (int mode = 0; mode < 3; ++mode) {
          update(0, jump[mode][end] + 1, dp[0][end + 1] + 1);
          for (int start = 0; start < end; ++start) {
            update(start + 1, jump[mode][end] + 1, dp[start + 1][end + 1] + 1);
            update(end + 1, jump[mode][start] + 1, dp[start + 1][end + 1] + 1);
          }
        }
//System.out.printf("dp[:%d]:[", end); for (int start = 0; start <= end; ++start) System.out.printf("%d,", dp[start][end + 1]); System.out.println();
      }
      int res = 0;
      for (int i = 0; i <= n; ++i) {
        res = Math.max(res, IntArrayUtils.max(dp[i]));
      }
      return res;
    }

    void update(int x, int y, int value) {
      if (x < y) {
        dp[x][y] = Math.max(dp[x][y], value);
      }
    }

    void initDis() {
      a7 = new int[n];
      aDis = new int[n];
      for (int i = 0; i < n; ++i) a7[i] = a[i] % 7;
      dis = new IntArrayList(n);
      dis.addAll(a);
      dis.sortAndUnique();
      for (int i = 0; i < n; ++i) aDis[i] = dis.lowerBound(a[i]);
    }

    void initStorage() {
      storageDis = new IntArrayList[dis.size];
      for (int i = 0; i < dis.size; ++i) storageDis[i] = new IntArrayList();
      storage7 = new IntArrayList[7];
      for (int i = 0; i < 7; ++i) storage7[i] = new IntArrayList();
    }

    void add(int idx) {
      storageDis[aDis[idx]].add(idx);
      storage7[a7[idx]].add(idx);
    }

    void remove(int idx) {
      Truth.assertThat(storageDis[aDis[idx]].pollLast() == idx);
      Truth.assertThat(storage7[a7[idx]].pollLast() == idx);
    }

    int calc(int mode, int idx) {
      switch (mode) {
        case 0:
          return calc0(idx);
        case 1:
          return calc1(idx);
        case 2:
          return calc2(idx);
      }
      Truth.fail();
      return -1;
    }

    int calc0(int idx) {
      int disIdx = aDis[idx];
      if (disIdx + 1 < dis.size && a[idx] + 1 == dis.get(disIdx + 1) && storageDis[disIdx + 1].isNotEmpty()) {
        return storageDis[disIdx + 1].peekLast();
      }
      return -1;
    }

    int calc1(int idx) {
      int disIdx = aDis[idx];
      if (disIdx > 0 && dis.get(disIdx - 1) + 1 == a[idx] && storageDis[disIdx - 1].isNotEmpty()) {
        return storageDis[disIdx - 1].peekLast();
      }
      return -1;
    }

    int calc2(int idx) {
      int idx7 = a7[idx];
      return storage7[idx7].isNotEmpty() ? storage7[idx7].peekLast() : -1;
    }

  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPosition;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPosition = 0;
      this.numberOfChars = 0;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public int[] nextInt(int n) {
      int[] res = new int[n];
      nextInt(n, res);
      return res;
    }

    public void nextInt(int n, int[] res) {
      for (int i = 0; i < n; ++i) {
        res[i] = nextInt();
      }
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPosition >= numberOfChars) {
        currentPosition = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPosition++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' ' || c == '\t' || isEndOfLineChar(c);
    }

    public boolean isEndOfLineChar(int c) {
      return c == '\n' || c == '\r' || c < 0;
    }

  }

  static interface IntCollection {
    int size();

    default boolean isNotEmpty() {
      return size() > 0;
    }

  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public QuickWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
      for (int i = 0; i < objects.length; ++i) {
        if (i > 0) {
          writer.print(' ');
        }
        writer.print(objects[i]);
      }
    }

    public void println(Object... objects) {
      print(objects);
      writer.print('\n');
    }

    public void close() {
      writer.close();
    }

  }

  static class Truth {
    public static void assertThat(boolean o) {
      if (!o) throw new IllegalArgumentException();
    }

    public static void fail() {
      throw new IllegalArgumentException();
    }

  }

  static class IntArrayList implements IntCollection, Iterable<Integer> {
    private static final int[] EMPTY = {};
    public int[] values;
    public int size;

    public IntArrayList() {
      values = EMPTY;
      clear();
    }

    public IntArrayList(int capacity) {
      values = new int[IntUtils.nextPow2(capacity)];
      clear();
    }

    public IntArrayList(Collection<Integer> collection) {
      this(collection.size());
      addAll(collection);
    }


    public void clear() {
      size = 0;
    }


    public int size() {
      return size;
    }


    public void add(int value) {
      ensureCapacity(size + 1);
      addInternal(value);
    }


    public void addAll(int[] values) {
      ensureCapacity(size + values.length);
      for (int value : values) {
        addInternal(value);
      }
    }


    public void addAll(Collection<Integer> values) {
      ensureCapacity(size + values.size());
      for (int value : values) {
        addInternal(value);
      }
    }

    public int peekLast() {
      return values[size - 1];
    }

    public int pollLast() {
      return values[--size];
    }

    public int get(int idx) {
      if (idx >= size) throw new ArrayIndexOutOfBoundsException();
      return values[idx];
    }

    public void sort() {
      IntArrayUtils.sort(values, 0, size);
    }

    public void unique() {
      size = IntArrayUtils.unique(values, 0, size);
    }

    public void sortAndUnique() {
      sort();
      unique();
    }

    public int lowerBound(int value) {
      return IntArrayUtils.lowerBound(values, 0, size, value);
    }

    public void ensureCapacity(int capacity) {
      if (capacity <= values.length) return;
      int[] newValues = new int[IntUtils.nextPow2(capacity)];
      for (int i = 0; i < size; ++i) {
        newValues[i] = values[i];
      }
      values = newValues;
    }


    public String toString() {
      return IntArrayUtils.toString(values, 0, size);
    }


    public Iterator<Integer> iterator() {
      return new Iterator<Integer>() {
        private int i = 0;


        public boolean hasNext() {
          return i < size;
        }


        public Integer next() {
          return values[i++];
        }
      };
    }

    private void addInternal(int value) {
      values[size++] = value;
    }

  }

  static class IntArrayUtils {
    private static final Random RANDOM = new Random(1000000007);

    public static int max(int[] values) {
      return max(values, 0, values.length);
    }

    public static int max(int[] values, int fromIdx, int toIdx) {
      int res = Integer.MIN_VALUE;
      for (int i = fromIdx; i < toIdx; ++i) {
        if (res < values[i]) res = values[i];
      }
      return res;
    }

    public static int unique(int[] values, int fromIdx, int toIdx) {
      if (fromIdx == toIdx) return 0;
      int res = 1;
      for (int i = fromIdx + 1; i < toIdx; ++i) {
        if (values[i - 1] != values[i]) {
          values[fromIdx + res++] = values[i];
        }
      }
      return res;
    }

    public static void sort(int[] values, int fromIdx, int toIdx) {
      shuffle(values, fromIdx, toIdx);
      Arrays.sort(values, fromIdx, toIdx);
    }

    public static int lowerBound(int[] values, int fromIdx, int toIdx, int value) {
      int res = toIdx;
      for (int lower = fromIdx, upper = toIdx - 1; lower <= upper; ) {
        int medium = (lower + upper) >> 1;
        if (value <= values[medium]) {
          res = medium;
          upper = medium - 1;
        } else {
          lower = medium + 1;
        }
      }
      return res;
    }

    public static void swap(int[] values, int uIdx, int vIdx) {
      if (uIdx == vIdx) return;
      values[uIdx] ^= values[vIdx];
      values[vIdx] ^= values[uIdx];
      values[uIdx] ^= values[vIdx];
    }

    public static void shuffle(int[] values, int fromIdx, int toIdx) {
      for (int i = toIdx - fromIdx - 1; i > 0; --i) {
        swap(values, i + fromIdx, RANDOM.nextInt(i + 1) + fromIdx);
      }
    }

    public static String toString(int[] values, int fromIdx, int toIdx) {
      StringBuilder sb = new StringBuilder("[");
      for (int i = fromIdx; i < toIdx; ++i) {
        if (i != fromIdx) sb.append(", ");
        sb.append(values[i]);
      }
      return sb.append("]").toString();
    }

  }

  static class IntUtils {
    public static boolean isPow2(int n) {
      return n > 0 && (n & (n - 1)) == 0;
    }

    public static int nextPow2(int n) {
      if (n < 1) return 1;
      return isPow2(n) ? n : Integer.highestOneBit(n) << 1;
    }

  }
}