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 double PI = acos(-1);
const double eps = 1e-12;
const int inf = 2000000000;
const long long int infLL = (long long int)2e18;
long long int MOD = 1000000007;
int MOD1 = 1000000007;
int MOD2 = 1000000009;
inline bool checkBit(long long int n, long long int i) {
  return n & (1LL << i);
}
inline long long int setBit(long long int n, long long int i) {
  return n | (1LL << i);
  ;
}
inline long long int resetBit(long long int n, long long int i) {
  return n & (~(1LL << i));
}
int dx[] = {0, 0, +1, -1};
int dy[] = {+1, -1, 0, 0};
inline bool EQ(double a, double b) { return fabs(a - b) < 1e-9; }
inline bool isLeapYear(long long int year) {
  return (year % 400 == 0) || (year % 4 == 0 && year % 100 != 0);
}
inline void normal(long long int &a) {
  a %= MOD;
  (a < 0) && (a += MOD);
}
inline long long int modMul(long long int a, long long int b) {
  a %= MOD, b %= MOD;
  normal(a), normal(b);
  return (a * b) % MOD;
}
inline long long int modAdd(long long int a, long long int b) {
  a %= MOD, b %= MOD;
  normal(a), normal(b);
  return (a + b) % MOD;
}
inline long long int modSub(long long int a, long long int b) {
  a %= MOD, b %= MOD;
  normal(a), normal(b);
  a -= b;
  normal(a);
  return a;
}
inline long long int modPow(long long int b, long long int p) {
  long long int r = 1LL;
  while (p) {
    if (p & 1) r = modMul(r, b);
    b = modMul(b, b);
    p >>= 1LL;
  }
  return r;
}
inline long long int modDiv(long long int a, long long int b) {
  return modMul(a, modPow(b, MOD - 2));
}
bool comp(const pair<long long int, pair<long long int, long long int> > &p1,
          const pair<long long int, pair<long long int, long long int> > &p2) {
  return p1.first > p2.first;
}
bool comp1(const pair<long long int, long long int> &p1,
           const pair<long long int, long long int> &p2) {
  if (p1.first == p2.first) {
    return p1.second > p2.second;
  }
  return p1.first < p2.first;
}
long long int converter(string a) {
  long long int i, mul = 1, r, t, ans = 0LL;
  if (a.length() == 0) return 0;
  for (i = a.length() - 1; i >= 0; i--) {
    t = a[i] - '0';
    r = t % 10;
    ans += (mul * r);
    mul = mul * 10;
  }
  return ans;
}
int msb(unsigned x) {
  union {
    double a;
    int b[2];
  };
  a = x;
  return (b[1] >> 20) - 1023;
}
int sum[10][1003];
int go[10][1003][130], n, a[1003];
int dp[260][1003];
int need;
void pre() {
  int i, j, k;
  for (i = 1; i <= n; ++i) {
    sum[a[i]][i] = 1;
    for (j = 1; j <= 8; ++j) sum[j][i] += sum[j][i - 1];
  }
  for (i = 1; i <= 8; ++i) {
    for (j = 1; j <= 128; ++j) {
      for (k = 1; k <= n; ++k) {
        int ans = inf, low = k, high = n, mid;
        while (low <= high) {
          mid = (low + high) >> 1;
          if (sum[i][mid] - sum[i][k - 1] >= j) {
            ans = min(ans, mid);
            high = mid - 1;
          } else
            low = mid + 1;
        }
        go[i][k][j] = ans;
      }
    }
  }
}
int solve(int mask, int idx) {
  if (idx > n) {
    if (__builtin_popcount(mask) == 8)
      return 0;
    else
      return -inf;
  }
  if (dp[mask][idx] != -1) return dp[mask][idx];
  int ret = -inf;
  for (int i = 0; i < 8; ++i) {
    if (checkBit(mask, i) == 0) {
      if (go[i + 1][idx][need] != inf) {
        ret = max(ret, need + solve(setBit(mask, i), go[i + 1][idx][need] + 1));
      }
      if (go[i + 1][idx][need + 1] != inf) {
        ret =
            max(ret, need + 1 +
                         solve(setBit(mask, i), go[i + 1][idx][need + 1] + 1));
      }
    }
  }
  ret = max(ret, solve(mask, idx + 1));
  return dp[mask][idx] = ret;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int i;
  cin >> n;
  set<int> s;
  for (i = 1; i <= n; ++i) {
    cin >> a[i];
    s.insert(a[i]);
  }
  pre();
  int ans = 0;
  for (i = 1; i <= 126; ++i) {
    memset(dp, -1, sizeof(dp));
    need = i;
    ans = max(ans, solve(0, 1));
  }
  cout << max((int)s.size(), ans) << '\n';
  return 0;
}
