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 maxn = 1e3 + 5;
int a[maxn], b[maxn];
int cnt[10];
int d[1010][8][200];
int vis[9];
int qwq = -1;
int check(int x) {
  int kkk = -1;
  for (int i = 0; i < (1 << 8); ++i) {
    int flag = 1, ans = 0, lst = 0;
    for (int j = 1; j <= 8; ++j) {
      int tmp = x;
      if (cnt[b[j]] < tmp) return -1;
      if (1 << (b[j] - 1) & i) ++tmp;
      if (cnt[b[j]] < tmp) {
        flag = 0;
        break;
      }
      if (d[lst + 1][b[j]][tmp] == -1) {
        flag = 0;
        break;
      }
      ans += tmp;
      lst = d[lst + 1][b[j]][tmp];
    }
    if (flag) {
      kkk = max(kkk, ans);
    }
  }
  return kkk;
}
void dfs(int step, int num) {
  if (step == 9) {
    qwq = max(qwq, check(num));
    return;
  }
  for (int i = 1; i <= 8; ++i) {
    if (!vis[i]) {
      vis[i] = 1;
      b[step] = i;
      dfs(step + 1, num);
      vis[i] = 0;
    }
  }
}
int c[9];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n, mn = (1 << 30), ans = 0;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    ++cnt[a[i]];
  }
  memset(d, -1, sizeof d);
  for (int i = 1; i <= n; ++i) {
    memset(c, 0, sizeof c);
    for (int j = i; j <= n; ++j) {
      if (c[a[j]] > mn) break;
      d[i][a[j]][++c[a[j]]] = j;
    }
  }
  for (int i = 1; i <= 8; ++i) {
    if (cnt[i]) ++ans;
    mn = min(cnt[i], mn);
  }
  int l = 1, r = mn;
  while (l < r) {
    int mid = (l + r) >> 1;
    qwq = -1;
    memset(vis, 0, sizeof vis);
    dfs(1, mid);
    int tmp = qwq;
    ans = max(ans, tmp);
    if (tmp != -1)
      l = mid + 1;
    else
      r = mid - 1;
  }
  qwq = -1;
  dfs(1, l);
  ans = max(qwq, ans);
  qwq = -1;
  dfs(1, r);
  ans = max(qwq, ans);
  cout << ans << '\n';
  return 0;
}
