Vladik was bored on his way home and decided to play the following game. He took n cards and put them in a row in front of himself. Every card has a positive integer number not exceeding 8 written on it. He decided to find the longest subsequence of cards which satisfies the following conditions:

  * the number of occurrences of each number from 1 to 8 in the subsequence doesn't differ by more then 1 from the number of occurrences of any other number. Formally, if there are ck cards with number k on them in the subsequence, than for all pairs of integers <image> the condition |ci - cj| ≤ 1 must hold. 
  * if there is at least one card with number x on it in the subsequence, then all cards with number x in this subsequence must form a continuous segment in it (but not necessarily a continuous segment in the original sequence). For example, the subsequence [1, 1, 2, 2] satisfies this condition while the subsequence [1, 2, 2, 1] doesn't. Note that [1, 1, 2, 2] doesn't satisfy the first condition. 



Please help Vladik to find the length of the longest subsequence that satisfies both conditions.

Input

The first line contains single integer n (1 ≤ n ≤ 1000) — the number of cards in Vladik's sequence.

The second line contains the sequence of n positive integers not exceeding 8 — the description of Vladik's sequence.

Output

Print single integer — the length of the longest subsequence of Vladik's sequence that satisfies both conditions.

Examples

Input

3
1 1 1


Output

1

Input

8
8 7 6 5 4 3 2 1


Output

8

Input

24
1 8 1 2 8 2 3 8 3 4 8 4 5 8 5 6 8 6 7 8 7 8 8 8


Output

17

Note

In the first sample all the numbers written on the cards are equal, so you can't take more than one card, otherwise you'll violate the first condition.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e3 + 5;
int n;
int nxt[10][MAX];
int sz[1 << 8];
vector<int> pos[10];
vector<int> perm;
inline bool ok(int k, int mask = 0) {
  int p = 0;
  for (auto &each : perm) {
    int idx = nxt[each][p];
    int kk = k + ((mask >> (each - 1)) & 1);
    if (kk == 0) {
      continue;
    }
    if (idx == -1 || (idx + kk > (int)pos[each].size())) {
      return false;
    }
    p = pos[each][idx + kk - 1];
  }
  return true;
}
int main() {
  scanf("%d", &n);
  for (int i = int(1); i < int(n + 1); i++) {
    int cur;
    scanf("%d", &cur);
    pos[cur].push_back(i);
  }
  memset(nxt, -1, sizeof nxt);
  for (int i = int(1); i < int(8 + 1); i++) {
    int ptr = 0;
    for (int j = int(0); j < int(n + 1); j++) {
      while (ptr < (int)pos[i].size() && pos[i][ptr] <= j) {
        ptr++;
      }
      if (ptr != (int)pos[i].size()) {
        nxt[i][j] = ptr;
      }
    }
  }
  for (int i = int(0); i < int(1 << 8); i++) {
    sz[i] = __builtin_popcount(i);
  }
  for (int i = int(1); i < int(8 + 1); i++) {
    perm.push_back(i);
  }
  int ans = 0;
  do {
    int left = 1, right = n;
    int best = 0;
    while (left <= right) {
      int mid = (left + right) / 2;
      if (ok(mid)) {
        best = mid;
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    ans = max(ans, best * 8);
    for (int i = int(1); i < int(1 << 8); i++) {
      if (ok(best, i)) {
        ans = max(ans, best * 8 + sz[i]);
      }
    }
  } while (next_permutation(perm.begin(), perm.end()));
  printf("%d\n", ans);
  return 0;
}
