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>
#pragma GCC target("sse2")
#pragma GCC optimization("O2")
#pragma GCC optimization("unroll-loops")
#pragma GCC optimize "trapv"
using namespace std;
const int maxn = 1000500;
inline int g() {
  int x;
  cin >> x;
  return x;
}
inline long long gl() {
  long long x;
  cin >> x;
  return x;
}
inline char gc() {
  char x;
  cin >> x;
  return x;
}
inline string gs() {
  string s;
  cin >> s;
  return s;
}
template <typename T>
inline vector<T> gv(int len) {
  vector<T> a(len);
  for (auto &it : a) cin >> it;
  return a;
}
inline vector<int> gv(int len) {
  vector<int> a(len);
  for (auto &it : a) cin >> it;
  return a;
}
inline vector<pair<int, int>> gv_andPairCnt(int len) {
  vector<pair<int, int>> a(len);
  int i = 1;
  for (auto &it : a) {
    it.second = i;
    i++;
    cin >> it.first;
  }
  return a;
}
double power_log(double power, double val) { return log(val) / log(power); }
template <typename T>
T sqr(T x) {
  return x * x;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (auto it : v) os << it << ", ";
  os << "\n";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &v) {
  os << "deque:{";
  for (auto it : v) os << it << " ";
  os << "}\n";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &v) {
  os << "set:{";
  for (auto it : v) os << it << " ";
  os << "}";
  return os;
}
template <typename T, typename T2>
ostream &operator<<(ostream &os, const map<T, T2> &v) {
  os << "map:{\n";
  for (auto it : v) os << "    {" << it.first << " <> " << it.second << "}\n";
  os << "}\n";
  return os;
}
template <typename T, typename T2>
ostream &operator<<(ostream &os, const pair<T, T2> &v) {
  os << "{" << v.first << ", " << v.second << "}";
  return os;
}
template <typename T, typename H>
inline vector<pair<T, H>> gv_andBiPair(int len) {
  vector<pair<T, H>> a(len);
  for (auto &it : a) {
    cin >> it.first >> it.second;
  }
  return a;
}
template <typename T>
inline set<T> vector_to_set(const vector<T> &vec) {
  set<T> s;
  for (auto &it : vec) s.insert(it);
  return s;
}
const long long md = 1e9 + 7;
int dp[1001][513], a[1010];
vector<int> arr[10];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n = g();
  for (int i = 1; i <= n; i++) {
    a[i] = g();
    arr[a[i]].push_back(i);
  }
  auto ok = [&](int mid) {
    memset(dp, -1, sizeof dp);
    for (int i = 1; i <= n; i++) {
      dp[i][0] = 0;
    }
    int ans = -1;
    for (int i = 1; i <= n; i++) {
      vector<int> pos1(10, -1), pos2(10, -1);
      for (int j = 1; j <= 8; j++) {
        auto it = lower_bound(arr[j].begin(), arr[j].end(), i) - arr[j].begin();
        if (mid == 0) {
          pos1[j] = i;
        } else {
          if (it + mid - 1 < arr[j].size() && arr[j][it + mid - 1] >= i) {
            pos1[j] = arr[j][it + mid - 1];
          }
        }
        if (it + mid < arr[j].size() && arr[j][it + mid] >= i) {
          pos2[j] = arr[j][it + mid];
        }
      }
      for (int msk = 0; msk < ((1 << 8)); ++msk) {
        if (dp[i][msk] == -1) {
          continue;
        }
        if (__builtin_popcount(msk) == 8) {
          ans = max(ans, dp[i][msk]);
        }
        for (int j = 0; j < (8); ++j) {
          if (((1 << j) & msk) == 0) {
            if (pos1[j + 1] != -1) {
              dp[pos1[j + 1]][msk | (1 << j)] =
                  max(dp[pos1[j + 1]][msk | (1 << j)], dp[i][msk] + mid);
            }
            if (pos2[j + 1] != -1) {
              dp[pos2[j + 1]][msk | (1 << j)] =
                  max(dp[pos2[j + 1]][msk | (1 << j)], dp[i][msk] + mid + 1);
            }
          }
        }
      }
    }
    return ans;
  };
  for (int i = n; i >= 0; i--) {
    int x = ok(i);
    if (x != -1) {
      cerr << i << endl;
      return cout << ok(i), 0;
    }
  }
}
