#include <bits/stdc++.h>
//#include "sequence.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;
const int N = 5e5 + 5;
int n, a[N], bit[N], s[N], t[N], c[N], id[N], st[N], ans;
vector<int> col[N];
void add(int i) {
for(; i <= n; i += i & -i) bit[i]++;
}
int get(int i) {
int ret = 0;
for(; i; i -= i & -i) ret += bit[i];
return ret;
}
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);
}
for(int k = 1; k <= n; k ++) if(!col[k].empty()) {
vector<int> rrh;
int sz = col[k].size();
// cerr << k << " " << sz << " d\n";
for(int i = 0; i < sz; i ++) {
int x = col[k][i];
t[x] = x - 2 * get(x);
t[x - 1] = x - 1 - 2 * get(x - 1);
}
for(int i = 0; i < sz; i ++) {
int x = col[k][i];
add(x);
s[x] = 2 * get(x) - x;
s[x - 1] = 2 * get(x - 1) - (x - 1);
// cerr << x << " " << s[x] << " " << t[x] << " " << s[x - 1] << " " << t[x - 1] << " k\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 = rrh.size();
for(int i = 1; i <= m; i ++) st[i] = sz;
auto update = [&](int x,int val) {
for(int i = x; i <= m; i += i & -i) st[i] = min(st[i], val);
};
auto query = [&](int x) {
int ret = m;
for(int i = x; i; i -= i & -i) ret = min(ret, st[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[c[ptr]]) - rrh.begin() + 1;
update(tmp, c[ptr] - 1);
}
int tmp = lower_bound(all(rrh), t[x]) - rrh.begin() + 1;
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
*/
//#define lpv
#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
