#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
using namespace std;
//#define lpv
#ifndef lpv
#include "sequence.h"
#endif // lpv
const int N = 5e5 + 5;
const int oo = 1e9;
int n, a[N], bit[N], s[N], t[N], c[N], id[N], ans;
vector<int> col[N];
struct node {
int lz, mx[2], mi[2];
} st[N << 2];
// 0 small - big
// 1 big - small
void build(int i,int l,int r) {
if(l == r) {
st[i].lz = 0;
st[i].mx[0] = st[i].mi[0] = -l;
st[i].mx[1] = st[i].mi[1] = l;
return;
}
int mid = (l + r) / 2;
build(i << 1, l, mid);
build(i << 1|1, mid + 1, r);
st[i].lz = 0;
for(int j = 0; j <= 1; j ++) {
st[i].mx[j] = max(st[i << 1].mx[j], st[i << 1|1].mx[j]);
st[i].mi[j] = min(st[i << 1].mi[j], st[i << 1|1].mi[j]);
}
}
void pro(int i,int x) {
st[i].lz += x;
st[i].mx[0] += 2 * x;
st[i].mi[0] += 2 * x;
st[i].mx[1] -= 2 * x;
st[i].mi[1] -= 2 * x;
}
void dolz(int i) {
if(!st[i].lz) return;
int x = st[i].lz; st[i].lz = 0;
pro(i << 1, x);
pro(i << 1|1, x);
}
void add(int i,int l,int r,int u,int v,int x) {
if(l > r || u > v || r < u || v < l) return;
if(u <= l && r <= v) {
pro(i, x);
return ;
}
dolz(i);
int mid = (l + r) / 2;
add(i << 1, l, mid, u, v, x);
add(i << 1|1, mid + 1, r, u, v, x);
st[i].lz = 0;
for(int j = 0; j <= 1; j ++) {
st[i].mx[j] = max(st[i << 1].mx[j], st[i << 1|1].mx[j]);
st[i].mi[j] = min(st[i << 1].mi[j], st[i << 1|1].mi[j]);
}
}
int get_max(int i,int l,int r,int u,int v, int type) {
if(l > r || u > v || r < u || v < l) return -oo;
if(u <= l && r <= v) return st[i].mx[type];
dolz(i);
int mid = (l + r) / 2;
return max(get_max(i << 1, l, mid, u, v, type), get_max(i << 1|1, mid + 1, r, u, v, type));
}
int get_min(int i,int l,int r,int u,int v,int type) {
if(l > r || u > v || r < u || v < l) return oo;
if(u <= l && r <= v) return st[i].mi[type];
dolz(i);
int mid = (l + r) / 2;
return min(get_min(i << 1, l, mid, u, v, type), get_min(i << 1|1, mid + 1, r, u, v, type));
}
int sequence(int _n, vector<int> A) {
n = _n;
ans = 1;
for(int i = 1; i <= n; i ++) {
a[i] = A[i - 1];
col[a[i]].push_back(i);
}
build(1, 1, n);
for(int k = 1; k <= n; k ++) if(!col[k].empty()) {
// if(k != 2) continue;
vector<int> rrh;
int sz = col[k].size();
int pre = 0;
for(int i = 0; i < sz; i ++) {
int x = col[k][i];
if(!pre) t[x - 1] = 0;
t[x - 1] = min(t[x - 1], get_min(1, 1, n, pre, x - 1, 1));
pre = x;
}
pre = n + 1;
for(int i = sz - 1; i >= 0; i --) {
int x = col[k][i];
t[x] = get_max(1, 1, n, x, pre - 1, 1);
pre = x;
}
for(int i = 0; i < sz; i ++) {
int x = col[k][i];
add(1, 1, n, x, n, 1);
}
pre = 0;
for(int i = 0; i < sz; i ++) {
int x = col[k][i];
if(!pre) s[x - 1] = 0;
s[x - 1] = min(s[x - 1], get_min(1, 1, n, pre, x - 1, 0));
pre = x;
}
// cerr << k << " st\n";
pre = n + 1;
for(int i = sz - 1; i >= 0; i --) {
int x = col[k][i];
s[x] = get_max(1, 1, n, x, pre - 1, 0);
pre = x;
// cerr << x << " " << s[x] << " " << t[x] << " " << s[x - 1] << " " << t[x - 1] << " h\n";
rrh.push_back(t[x]);
rrh.push_back(t[x - 1]);
c[i] = i;
id[i] = i;
}
sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin());
sort(c, c + sz, [&](int x,int y){return (s[col[k][x] - 1] == s[col[k][y] - 1] ? col[k][x] - 1 < col[k][y] - 1 : s[col[k][x] - 1] < s[col[k][y] - 1]);});
sort(id, id + sz, [&](int x,int y){return (s[col[k][x]] == s[col[k][y]] ? col[k][x] < col[k][y] : s[col[k][x]] < s[col[k][y]]);});
int ptr = -1;
int m = (int)rrh.size();
for(int i = 1; i <= m; i ++) bit[i] = m;
auto update = [&](int x,int val) {
for(int i = x; i <= m; i += i & -i) bit[i] = min(bit[i], val);
};
auto query = [&](int x) {
int ret = m;
for(int i = x; i; i -= i & -i) ret = min(ret, bit[i]);
return ret;
};
for(int i = 0; i < sz; i ++) {
int x = col[k][id[i]];
int pos = id[i];
// cerr << i << " " << pos << " " << x << " c\n";
while(ptr < sz - 1 && s[col[k][c[ptr + 1]] - 1] <= s[x]) {
ptr++;
int tmp = lower_bound(all(rrh), t[col[k][c[ptr]] - 1]) - rrh.begin() + 1;
// cerr << tmp << " " << c[ptr] - 1 << " " << t[c[ptr]] << " update\n";
update(tmp, c[ptr] - 1);
}
// cerr << ptr << " " << c[ptr] << " u\n";
int tmp = lower_bound(all(rrh), t[x]) - rrh.begin() + 1;
// cerr << tmp << " " << query(tmp) << " ask\n";
ans = max(ans, pos - query(tmp));
}
}
return ans;
}
/*
7
1 2 3 1 2 1 3
3
9
1 1 2 3 4 3 2 1 1
2
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
3
*/
#ifdef lpv
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")) {
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
int _n; cin >> _n;
vector<int> A;
for(int i = 1; i <= _n; i ++) {
int x; cin >> x;
A.push_back(x);
}
int result = sequence(_n, A);
cout << result;
}
#endif // lpv
