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 <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& _p) {
  return os << "(" << _p.first << "," << _p.second << ")";
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& _V) {
  bool f = true;
  os << "[";
  for (auto v : _V) {
    os << (f ? "" : ",") << v;
    f = false;
  }
  return os << "]";
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& _S) {
  bool f = true;
  os << "(";
  for (auto s : _S) {
    os << (f ? "" : ",") << s;
    f = false;
  }
  return os << ")";
}
template <typename T, typename U>
ostream& operator<<(ostream& os, const map<T, U>& _M) {
  return os << set<pair<T, U>>(_M.begin(), _M.end());
}
const signed long long INF = 1000000100;
const long double EPS = 1e-9;
const int MAXN = 1042;
const int K = 8, MAXL = 125;
int a[MAXN], jump[K + 1][MAXN][MAXL + 5];
int n;
int answer;
int check(vector<int>& perm, vector<int>& cnt) {
  int i = 1;
  int sum = 0;
  for (int c : cnt) sum += c;
  for (int k : perm) {
    if (cnt[k] > MAXL) return 0;
    if (i > n && cnt[k]) return 0;
    if (cnt[k]) i = jump[k][i][cnt[k]];
    if (i > n + 1) return 0;
  }
  return 1;
}
int solve(vector<int>& perm) {
  int ans = 0;
  int st = -1, en = MAXL + 1;
  vector<int> cnt(K + 1);
  while (st + 1 < en) {
    int shot = (st + en) / 2;
    int best = -1;
    for (int(mask) = (0); (mask) < ((1 << K)); (mask)++) {
      int cur_sum = 0;
      for (int(j) = (0); (j) < (K); (j)++) {
        cnt[j + 1] = shot;
        if (mask & (1 << j)) cnt[j + 1]++;
        cur_sum += cnt[j + 1];
      }
      if (mask != 0 && (cur_sum <= best || cur_sum <= answer)) continue;
      if (check(perm, cnt)) {
        best = max(best, cur_sum);
      } else if (mask == 0)
        break;
    }
    ans = max(ans, best);
    answer = max(answer, ans);
    if (best >= 0)
      st = shot;
    else
      en = shot;
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n;
  for (int(i) = (1); (i) <= (n); (i)++) cin >> a[i];
  for (int(k) = (1); (k) <= (K); (k)++) {
    for (int(i) = (1); (i) <= (n); (i)++) {
      int j = i;
      jump[k][i][0] = i;
      for (int(l) = (1); (l) <= (MAXL + 1); (l)++) {
        while (j <= n && a[j] != k) j++;
        j++;
        jump[k][i][l] = j;
        if (l <= 2) {
          if (0)
            cout << "jump " << k << " " << i << " " << l << " : " << j << endl;
        }
      }
    }
  }
  vector<int> perm(K);
  for (int(i) = (1); (i) <= (K); (i)++) perm[i - 1] = i;
  answer = 0;
  while (42) {
    answer = max(answer, solve(perm));
    if (!next_permutation(perm.begin(), perm.end())) break;
  }
  cout << answer << "\n";
}
