#include <bits/stdc++.h>
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maxi(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
if (a > b) { a = b; return 1; } return 0;
}
const int N = (int)5e5 + 7;
int n, a[N];
namespace SUB1 {
struct CTDL {
multiset<int> a, b;
void add(int x) {
if (sz(a) <= sz(b)) a.insert(x);
else b.insert(x);
if (sz(a) and sz(b) and *a.rbegin()>*b.begin()){
int x=*a.rbegin(), y=*b.begin();
a.erase(a.find(x));
b.erase(b.find(y));
a.insert(y);
b.insert(x);
}
}
int med() {
return *a.rbegin();
}
int med2() {
return *b.begin();
}
};
int sol() {
int ans = 0;
vec<int> cnt(n + 1, 0);
FOR(i, 1, n) {
CTDL s;
FOR(j, i, n) {
++cnt[a[j]];
s.add(a[j]);
ans = max(ans, cnt[s.med()]);
if ( (j - i + 1) % 2 == 0 )
ans = max(ans, cnt[s.med2()]);
}
FOR(j, i, n) {
--cnt[a[j]];
}
}
return ans;
}
};
namespace SUB2 {
bool check() {
vec<bool> okl(n + 1, 0), okr(n + 1, 0);
okl[1] = 1;
FOR(i, 2, n) {
okl[i] = okl[i - 1] and (a[i] >= a[i-1]);
}
okr[n] = 1;
FOD(i, n - 1, 1) {
okr[i] = okr[i + 1] and (a[i] >= a[i + 1]);
}
FOR(i, 1, n) {
if (okl[i] and okr[i])
return 1;
}
return 0;
}
int sol() {
int ans = 0;
vec<int> cnt(n + 1, 0);
vec<ii> b;
FOR(i, 1, n) {
int j = i;
while (j + 1 <= n and a[j + 1] == a[i])
++j;
b.push_back(_mp(a[i], j - i + 1));
cnt[a[i]] += j - i + 1;
ans = max(ans, j - i + 1);
i = j;
}
sort(all(b));
int g = 0;
for(int i = sz(b) - 1; i >= 0; --i) {
ii j = b[i];
int v = j.fi, c = j.se;
if (c!=cnt[v]) {
int k=g;
int p=cnt[v];
int j=n-(k+p);
if (j >= k - p) {
ans = max(ans, cnt[v]);
}
// cerr << v << ' ' << k << ' ' << p << ' ' << j << nl;
}
g+=cnt[v];
if (i > 0 and b[i].fi==b[i-1].fi)
--i;
}
return ans;
}
};
namespace SUB5 {
struct IT {
int n;
vec<ii> t;
vec<int> lz;
IT (){};
IT (int _n) {
n = _n;
lz.resize(4 * n + 7);
t.resize(4 * n + 7);
}
vec<int> a;
void refine(int id) {
t[id].fi = min(t[id << 1].fi, t[id << 1 | 1].fi);
t[id].se = max(t[id << 1].se, t[id << 1 | 1].se);
}
void build(int id, int l, int r) {
if (l == r) {
return void(t[id]=_mp(a[l], a[l]));
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
refine(id);
}
void init(vec<int> p){
a.resize(n + 1);
FOR(i, 1, n) a[i] = p[i];
build(1, 1, n);
}
void push(int id) {
int &x = lz[id];
t[id<<1].fi+=x;
t[id<<1|1].fi+=x;
t[id<<1].se+=x;
t[id<<1|1].se+=x;
lz[id<<1]+=x;
lz[id<<1|1]+=x;
x=0;
}
void update(int id, int l, int r, int u, int v, int val) {
if (l > v or r < u) return ;
if (l >= u and r <= v) {
t[id].fi += val;
t[id].se += val;
lz[id] += val;
return ;
}
if (lz[id]) {
push(id);
}
int m = (l + r) >> 1;
update(id << 1, l, m, u, v, val);
update(id << 1 | 1, m + 1, r, u, v, val);
refine(id);
}
void update(int l, int r, int v) {
if (l > r) return ;
update(1, 1, n, l, r, v);
}
ii get(int id, int l, int r, int u, int v) {
if (l > v or r < u) {
return _mp(n, -n);
}
if (l >= u and r <= v)
return t[id];
if (lz[id]) {
push(id);
}
int m = (l + r) >> 1;
ii A = get(id << 1, l, m, u, v);
ii B = get(id << 1 | 1, m + 1, r, u, v);
return _mp(min(A.fi, B.fi), max(A.se, B.se));
}
ii get(int l, int r) {
return get(1, 1, n, l, r);
}
};
vec<int> pos[N];
bool check() {
vec<int> cnt(n + 1, 0);
FOR(i, 1, n) ++cnt[a[i]];
if (*max_element(all(cnt)) > 2)
return 0;
return 1;
}
int sol() {
FOR(i, 1, n - 1) if (a[i] == a[i+1])
return 2;
int ans = 1;
FOR(i, 1, n) {
pos[a[i]].push_back(i);
}
IT st1(n), st2(n);
vec<int> p(n+1,0);
FOR(i,1,n)p[i]=-(i-1);
st1.init(p); // pref(l-1)
FOR(i,1,n)p[i]=-i;
st2.init(p); // pref(r)
FOR(i, 1, n) if (sz(pos[i])) {
if (sz(pos[i]) == 2) {
int x = pos[i][0], y = pos[i][1];
ii A = st1.get(1,x);
assert(A.fi <= A.se);
// cerr << A.fi << ' ' << A.se<< nl;
A.fi-=4;
ii B = st2.get(y,n);
// cerr << B.fi << ' ' << B.se << nl;
// cerr << x << ' ' << y << nl;
if (!(A.fi > B.se or A.se < B.fi)) {
ans=2;
return ans;
}
}
for(int j : pos[i]) {
//pref(j+1) duoc cong them 2
st1.update(j + 1, n, 2);
st2.update(j, n, 2);
}
}
return 1;
}
};
int sequence(int N, vector<int> A) {
n = N;
FOR(i, 1, n) a[i] = A[i - 1];
if (n <= 2000) {
return SUB1::sol();
}
if (SUB2::check()) {
return SUB2::sol();
}
if (SUB5::check()) {
return SUB5::sol();
}
return 0;
}
#ifdef LOCAL
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("main.inp", "r", stdin);
freopen("main.out", "w", stdout);
int n; cin >> n;
vector<int> a(n);
for(int & x : a) cin >> x;
cout << sequence(n, a);
}
#endif LOCAL
