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;
template <class C>
void min_self(C &a, C b) {
  a = min(a, b);
}
template <class C>
void max_self(C &a, C b) {
  a = max(a, b);
}
const long long MOD = 1000000007;
long long mod(long long n, long long m = MOD) {
  n %= m;
  if (n < 0) n += m;
  return n;
}
const int MAXN = 1e5 + 5;
const int LOGN = 21;
const long long INF = 1e14;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
template <class T1, class T2>
void add(T1 &x, T2 y, long long m = MOD) {
  x += y;
  if (x >= m) x -= m;
}
template <class T1, class T2>
void sub(T1 &x, T2 y, long long m = MOD) {
  x -= y;
  if (x < 0) x += m;
}
const int MX = (1 << 8);
int dp[1005][MX];
int prv[1005][10];
int jump[10][1005];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 10; j++) prv[i][j] = prv[i - 1][j];
    prv[i][a[i - 1]] = i - 1;
    jump[0][i] = prv[i][a[i]];
    for (int j = 1; j < 10; j++) {
      int x = jump[j - 1][i];
      jump[j][i] = jump[j - 1][x];
    }
  }
  auto go = [&](int index, int len) {
    if (len <= 0) return index;
    int st = index;
    for (int j = 10; j >= 0; j--) {
      if ((len >> j) & 1) st = jump[j][st];
    }
    return st;
  };
  int ans = 0;
  set<int> have;
  for (int i = 1; i <= n; i++) have.insert(a[i]);
  ans = max(ans, (int)have.size());
  for (int low = 1; low <= n; low++) {
    for (int i = 0; i <= n; i++)
      for (int mask = 0; mask < MX; mask++) dp[i][mask] = -MOD;
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
      for (int mask = 0; mask < MX; mask++) {
        max_self(dp[i][mask], dp[i - 1][mask]);
        if (((mask >> (a[i] - 1)) & 1) == 0) continue;
        int other = mask ^ (1 << (a[i] - 1));
        int where = go(i, low - 1);
        if (where >= 1) {
          max_self(dp[i][mask], dp[where][other] + low);
        }
        where = prv[where][a[i]];
        if (where >= 1) max_self(dp[i][mask], dp[where][other] + low + 1);
      }
    }
    max_self(ans, dp[n][MX - 1]);
  }
  cout << ans, cout << "\n";
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}
