This is the easy version of the problem. The difference between the versions is in the constraints on the array elements. You can make hacks only if all versions of the problem are solved.

You are given an array [a_1, a_2, ..., a_n]. 

Your goal is to find the length of the longest subarray of this array such that the most frequent value in it is not unique. In other words, you are looking for a subarray such that if the most frequent value occurs f times in this subarray, then at least 2 different values should occur exactly f times.

An array c is a subarray of an array d if c can be obtained from d by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The first line contains a single integer n (1 ≤ n ≤ 200 000) — the length of the array.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ min(n, 100)) — elements of the array.

Output

You should output exactly one integer — the length of the longest subarray of the array whose most frequent value is not unique. If there is no such subarray, output 0.

Examples

Input


7
1 1 2 2 3 3 3


Output


6

Input


10
1 1 1 5 4 1 3 1 2 2


Output


7

Input


1
1


Output


0

Note

In the first sample, the subarray [1, 1, 2, 2, 3, 3] is good, but [1, 1, 2, 2, 3, 3, 3] isn't: in the latter there are 3 occurrences of number 3, and no other element appears 3 times.
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T sqr(T x) {
  return x * x;
}
const double EPS = 1e-11;
const int INF = 1000 * 1000 * 1000;
const long long LINF = INF * 1ll * INF;
const double DINF = 1e200;
const double PI = 3.1415926535897932384626433832795l;
int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
long long gcd(long long a, long long b) { return a ? gcd(b % a, a) : b; }
long long gcdex(long long a, long long b, long long &x, long long &y) {
  if (!a) {
    x = 0, y = 1;
    return b;
  }
  long long k = b / a;
  long long g = gcdex(b - k * a, a, y, x);
  x -= k * y;
  return g;
}
long long inv(long long a, long long m) {
  assert(m > 1);
  long long x, y, g;
  g = gcdex(a, m, x, y);
  return (x % (m / g) + m / g) % m / g;
}
long long crt(long long a1, long long m1, long long a2, long long m2) {
  long long a = (a2 - a1 % m2 + m2) % m2;
  long long x, y, g;
  g = gcdex(m1, m2, x, y);
  if (a % g) return -1;
  long long m = m1 / g * m2;
  assert(x + m2 >= 0);
  x = a / g * (x + m2) % m2;
  long long r = (a1 + x * m1) % m;
  assert(r % m1 == a1 && r % m2 == a2);
  return r;
}
long long powmod(long long a, long long p, long long m) {
  assert(p >= 0);
  long long r = 1;
  while (p) {
    if (p & 1) r = r * a % m;
    p >>= 1;
    a = a * a % m;
  }
  return r;
}
long long mulmod(long long a, long long b, long long m) {
  assert(a >= 0 && b >= 0 && m > 0 && a < m && b < m);
  if (b < a) swap(a, b);
  if (m < INF * 2 || a <= 1) return a * b % m;
  long long q = m / a, r = m % a;
  long long v = a * (b % q) - (r < q ? r * (b / q) : mulmod(r, b / q, m));
  if (v < 0) {
    v += m;
    assert(v >= 0);
  }
  return v;
}
long long powmod2(long long a, long long p, long long m) {
  a %= m;
  long long r = 1;
  while (true) {
    if (p & 1) r = mulmod(r, a, m);
    p >>= 1;
    if (p)
      a = mulmod(a, a, m);
    else
      break;
  }
  return r;
}
bool isprime(long long a) {
  if (a <= 1) return false;
  for (long long i = 2; i * i <= a; ++i) {
    if (a % i == 0) return false;
  }
  return true;
}
long long sqrtup(long long a) {
  if (!a) return 0;
  long long x = max(0ll, (long long)sqrt((double)a));
  while (x * x >= a) --x;
  while ((x + 1) * (x + 1) < a) ++x;
  return x + 1;
}
long long isqrt(long long a) {
  if (a <= 0) {
    assert(!a);
    return 0;
  }
  long long x = (long long)sqrt((double)a);
  while (sqr(x + 1) <= a) ++x;
  while (x * x > a) --x;
  return x;
}
long long sgn(long long x) { return x < 0 ? -1 : x > 0 ? 1 : 0; }
double randf() {
  double m = RAND_MAX + 1.;
  return (((rand() + .5) / m + rand()) / m + rand()) / m;
}
int rand30() {
  assert(RAND_MAX >= (1 << 15) - 1);
  return (
      int)((((uint32_t)rand()) * (1u + (uint32_t)RAND_MAX) + (uint32_t)rand()) &
           ((1u << 30) - 1));
}
template <class T>
void smin(T &a, T b) {
  a = min(a, b);
}
template <class T>
void smax(T &a, T b) {
  a = max(a, b);
}
template <class T>
ostream &operator<<(ostream &s, const vector<T> &v);
template <class A, class B>
ostream &operator<<(ostream &s, const pair<A, B> &p);
template <class K, class V>
ostream &operator<<(ostream &s, const map<K, V> &m);
template <class T>
ostream &operator<<(ostream &s, const set<T> &m);
template <class T, size_t N>
ostream &operator<<(ostream &s, const array<T, N> &a);
template <class... T>
ostream &operator<<(ostream &s, const tuple<T...> &t);
template <class T>
ostream &operator<<(ostream &s, const vector<T> &v) {
  s << '[';
  for (int i = 0; i < (((int)(v).size())); ++i) {
    if (i) s << ',';
    s << v[i];
  }
  s << ']';
  return s;
}
template <class A, class B>
ostream &operator<<(ostream &s, const pair<A, B> &p) {
  s << "(" << p.first << "," << p.second << ")";
  return s;
}
template <class K, class V>
ostream &operator<<(ostream &s, const map<K, V> &m) {
  s << "{";
  bool f = false;
  for (const auto &it : m) {
    if (f) s << ",";
    f = true;
    s << it.first << ": " << it.second;
  }
  s << "}";
  return s;
}
template <class T>
ostream &operator<<(ostream &s, const set<T> &m) {
  s << "{";
  bool f = false;
  for (const auto &it : m) {
    if (f) s << ",";
    f = true;
    s << it;
  }
  s << "}";
  return s;
}
template <class T>
ostream &operator<<(ostream &s, const multiset<T> &m) {
  s << "{";
  bool f = false;
  for (const auto &it : m) {
    if (f) s << ",";
    f = true;
    s << it;
  }
  s << "}";
  return s;
}
template <class T, class V, class C>
ostream &operator<<(ostream &s, const priority_queue<T, V, C> &q) {
  auto a = q;
  s << "{";
  bool f = false;
  while (!a.empty()) {
    if (f) s << ",";
    f = true;
    s << a.top();
    a.pop();
  }
  return s << "}";
}
template <class T, size_t N>
ostream &operator<<(ostream &s, const array<T, N> &a) {
  s << '[';
  for (int i = 0; i < (((int)(a).size())); ++i) {
    if (i) s << ',';
    s << a[i];
  }
  s << ']';
  return s;
}
template <class T>
ostream &operator<<(ostream &s, const deque<T> &a) {
  s << '[';
  for (int i = 0; i < (((int)(a).size())); ++i) {
    if (i) s << ',';
    s << a[i];
  }
  s << ']';
  return s;
}
template <size_t n, class... T>
struct put1 {
  static ostream &put(ostream &s, const tuple<T...> &t) {
    s << get<sizeof...(T) - n>(t);
    if (n > 1) s << ',';
    return put1<n - 1, T...>::put(s, t);
  }
};
template <class... T>
struct put1<0, T...> {
  static ostream &put(ostream &s, const tuple<T...> &t) { return s; }
};
template <class... T>
ostream &operator<<(ostream &s, const tuple<T...> &t) {
  s << "(";
  put1<sizeof...(T), T...>::put(s, t);
  s << ")";
  return s;
}
ostream &put3(ostream &s, const char *, bool) { return s; }
template <class U, class... T>
ostream &put3(ostream &s, const char *f, bool fs, U &&u, T &&...t) {
  while (*f == ' ') ++f;
  if (!fs) s << ", ";
  auto nf = f;
  int d = 0;
  while (*nf && (*nf != ',' || d)) {
    if (*nf == '(')
      ++d;
    else if (*nf == ')')
      --d;
    ++nf;
  }
  auto nf2 = nf;
  while (nf2 > f && *(nf2 - 1) == ' ') --nf;
  fs = *f == '"';
  if (!fs) {
    s.write(f, nf2 - f);
    s << "=";
  };
  s << u;
  if (fs) s << ' ';
  if (*nf) ++nf;
  return put3(s, nf, fs, forward<T>(t)...);
}
mt19937 mtrng;
int subsolve(const vector<int> &D0, const vector<int> &P0,
             const vector<int> &P1, const vector<int> &A, int v0, int v1) {
  vector<int> V;
  for (int i = 0; i < (((int)(P1).size()) - 1); ++i) {
    int p = P1[i];
    V.push_back(i - D0[p]);
    V.push_back(i + 1 - D0[p]);
  }
  V.push_back(((int)(P1).size()) - ((int)(P0).size()));
  sort((V).begin(), (V).end());
  V.erase(unique((V).begin(), (V).end()), V.end());
  vector<int> U1(((int)(V).size()), INF), U2(((int)(V).size()), -INF);
  int pr = 0, d = 0,
      vi = upper_bound((V).begin(), (V).end(), 0) - V.begin() - 1;
  for (int i = 0; i < (((int)(P1).size())); ++i) {
    int p = P1[i];
    while (pr <= p) {
      assert(d == i - D0.at(pr));
      if (d != V.at(vi)) {
        assert(d > V[vi]);
        pr = P0.at(D0[pr] + d - V[vi] - 1) + 1;
        assert(pr <= p);
        d = V[vi];
        continue;
      }
      int p2 = min(p, P0.at(D0.at(pr)));
      assert(p2 >= pr);
      smin(U1[vi], pr);
      smax(U2[vi], p2);
      if (p2 < p) {
        --d;
        --vi;
      }
      pr = p2 + 1;
    }
    assert(pr == p + 1);
    assert(d == V[vi]);
    ++d;
    ++vi;
    if (i + 1 < ((int)(P1).size())) assert(d == V.at(vi));
  }
  int ans = 0;
  for (int i = 0; i < (((int)(U1).size())); ++i) {
    assert(U1[i] != INF && U2[i] != -INF);
    assert(U2[i] >= U1[i]);
    smax(ans, U2[i] - U1[i]);
  }
  return ans;
}
int solve(vector<int> A) {
  int n = ((int)(A).size());
  vector<int> C(n + 1);
  vector<pair<int, int> > V(n);
  for (int i = 0; i < (n); ++i) {
    ++C[A[i]];
    V[i] = make_pair(A[i], i);
  }
  pair<int, int> mx(-1, -1);
  for (int i = 0; i < (((int)(C).size())); ++i) smax(mx, make_pair(C[i], i));
  assert(mx.second != -1);
  vector<int> P0, D0(n + 1);
  for (int i = 0; i < (n); ++i) {
    D0[i + 1] = D0[i];
    if (A[i] == mx.second) {
      P0.push_back(i);
      ++D0[i + 1];
    }
  }
  P0.push_back(n);
  sort((V).begin(), (V).end());
  int ans = 0;
  for (int i = 0; i < n;) {
    int ii = i + 1;
    while (ii < n && V[ii].first == V[i].first) ++ii;
    if (V[i].first != mx.second) {
      vector<int> P(ii - i);
      for (int q = 0; q < (ii - i); ++q) P[q] = V[i + q].second;
      P.push_back(n);
      smax(ans, subsolve(D0, P0, P, A, mx.second, V[i].first));
    }
    i = ii;
  }
  return ans;
}
void stress() {
  for (int n = 1; n <= 100; ++n) {
    vector<int> A(n);
    for (int qq = 0; qq < (10000); ++qq) {
      for (int i = 0; i < (n); ++i) A[i] = rand() % 2;
      solve(A);
    }
  }
  do {
  } while (false);
}
int main(int argc, char **argv) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(20);
  srand(35964);
  mtrng.seed(765674737);
  int n;
  cin >> n;
  vector<int> A(n);
  for (int i = 0; i < (n); ++i) cin >> A[i];
  cout << solve(A);
  return 0;
}
