#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <chrono>
#include <random>
#include <complex>
#include <numeric>
#include <assert.h>
#include <functional>
#include <climits>
#include <cstring>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ushort = unsigned short;
#ifndef LOCAL
#define endl "\n"
#endif
#define f first
#define s second
#define vec vector
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
template<typename T1, typename T2>
istream& operator>> (istream &in, pair<T1, T2> &p) { in >> p.f >> p.s; return in; }
template<typename T1, typename T2>
ostream& operator<< (ostream &out, pair<T1, T2> p) { out << "(" << p.f << " " << p.s << ")"; return out; }
#define printv(v) cerr << #v << " "; for (auto &x : v) { cerr << x << " "; } cerr << endl;
#define printvv(v) cerr << #v << " "; for (auto &x : v) { for (auto &y : x) { cerr << y << " "; } cerr << endl; }
#define debug(x) cerr << #x << " " << x << endl;
template<typename T>
istream& operator>> (istream &in, vector<T> &v) {
for (auto &x : v) {
in >> x;
}
return in;
}
template<typename T>
ostream& operator<< (ostream &out, vector<T> v) {
for (auto &x : v) {
out << x << " ";
}
return out;
}
template<typename T>
void operator-=(vector<T> &v, int delta) {
for (auto &x : v) {
x -= delta;
}
}
template<typename T>
void operator+=(vector<T> &v, int delta) {
for (auto &x : v) {
x += delta;
}
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int MAX_N = (1<<20);
struct Node {
int mn, mx, sm;
Node() {
mn = 0;
mx = 0;
sm = 0;
};
};
Node T[MAX_N * 2];
void merge(int i) {
T[i].mn = min(T[i * 2].mn, T[i * 2].sm + T[i * 2 + 1].mn);
T[i].mx = max(T[i * 2].mx, T[i * 2].sm + T[i * 2 + 1].mx);
T[i].sm = T[i * 2].sm + T[i * 2 + 1].sm;
}
void update(int i, int x) {
i += MAX_N;
T[i].sm = x;
T[i].mn = min(x, 0);
T[i].mx = max(x, 0);
i /= 2;
while (i) {
merge(i);
i /= 2;
}
}
Node get(int i, int l, int r, int ql, int qr) {
if (l >= qr) {
return T[0];
}
if (r <= ql) {
return T[i];
}
if (ql <= l && r <= qr) {
return T[i];
} else {
int m = (l + r) / 2;
Node a = get(i * 2, l, m, ql, qr);
Node b = get(i * 2 + 1, m, r, ql, qr);
if (m > ql) {
b.mn = min(a.mn, a.sm + b.mn);
b.mx = max(a.mx, a.sm + b.mx);
} else {
b.mn = a.sm + b.mn;
b.mx = a.sm + b.mx;
}
b.sm = a.sm + b.sm;
return b;
}
}
int F[MAX_N * 2], F2[MAX_N * 2];
void updateF(int i) {
for (; i < MAX_N * 2; i = (i|(i + 1))) {
F[i] = 1e9;
}
}
void updateF2(int i) {
for (; i < MAX_N * 2; i = (i|(i + 1))) {
F2[i] = -1e9;
}
}
void updateF(int i, int x) {
for (; i < MAX_N * 2; i = (i|(i + 1))) {
F[i] = min(F[i], x);
}
}
void updateF2(int i, int x) {
for (; i < MAX_N * 2; i = (i|(i + 1))) {
F2[i] = max(F2[i], x);
}
}
int getF(int r) {
int ans = 1e9;
for (; r >= 0; r = (r&(r+1))-1) {
ans = min(ans, F[r]);
}
return ans;
}
int getF2(int r) {
int ans = -1e9;
for (; r >= 0; r = (r&(r+1))-1) {
ans = max(ans, F2[r]);
}
return ans;
}
int solve(int n, vector<int> &a) {
T[0].mn = 1e9;
T[0].mx = -1e9;
for (int i = MAX_N * 2 - 1; i >= MAX_N; --i) {
T[i].mn = 0;
T[i].mx = 1;
T[i].sm = 1;
}
for (int i = MAX_N - 1; i > 0; --i) {
merge(i);
}
for (int i = 0; i < MAX_N * 2; ++i) {
F[i] = 1e9;
F2[i] = -1e9;
}
vector<vector<int>> p(n + 1);
for (int i = 0; i < n; ++i) {
p[a[i]].pb(i);
}
int ans = 1;
vector<int> td, td2;
vector<pii> L;
td.reserve(n * 2);
td2.reserve(n);
L.resize(n * 2);
for (int x = 1; x <= n; ++x) {
if (p[x].size() > ans) {
for (auto &y: p[x]) {
update(y, 0);
}
for (int q = 0; q <= p[x].size(); ++q) {
int l = 0, r = n;
if (q != p[x].size()) {
r = p[x][q] + 1;
}
if (q != 0) {
l = p[x][q - 1];
}
Node a = get(1, 0, MAX_N, l, r);
L[q] = mp(a.mn, a.mx);
}
auto check = [&](int nans) {
while (!td.empty()) {
updateF(td.back());
td.pop_back();
}
while (!td2.empty()) {
updateF2(td2.back());
td2.pop_back();
}
for (int q = 0; q <= p[x].size(); ++q) {
if (q >= nans) {
updateF(MAX_N - L[q - nans].f + (q - nans), L[q - nans].f + (q - nans));
updateF(MAX_N - L[q - nans].s + (q - nans), L[q - nans].s + (q - nans));
updateF2(L[q - nans].f + MAX_N, L[q - nans].s);
td.pb(MAX_N - L[q - nans].f + (q - nans));
td.pb(MAX_N - L[q - nans].s + (q - nans));
td2.pb(L[q - nans].f + MAX_N);
}
if (getF(MAX_N - L[q].f + q) <= L[q].s + q || getF2(MAX_N + L[q].f) >= L[q].f) {
return true;
}
}
return false;
};
int lg = 0;
while (check(ans + (1<<lg))) {
++lg;
}
if (lg > 0) {
ans += (1 << (lg - 1));
while (--lg) {
if (check(ans + (1 << (lg - 1)))) {
ans += (1 << (lg - 1));
}
}
}
}
for (auto &y : p[x]) {
update(y, -1);
}
}
return ans;
}
int sequence(int n, vector<int> a) {
return solve(n, a);
}
#ifdef LOCAL
int main() {
freopen("in.txt", "r", stdin);
int N;
assert(1 == scanf("%d", &N));
std::vector<int> A(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &A[i]));
}
int result = sequence(N, A);
printf("%d\n", result);
return 0;
}
#endif
