#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
using ii = pair<int, int>;
template <class T, T (*merge)(T, T), T def = T()>
struct Segtree {
vector<T> tree, lazy;
int _n;
Segtree() {}
Segtree(int N){
setup(N);
}
void setup(int N){
tree.assign(4 * N, T());
lazy.assign(4 * N, T());
_n = N;
}
void apply(int i, T delta){
tree[i] += delta;
lazy[i] += delta;
}
void push(int i){
if (lazy[i] == T()) return;
apply(i<<1, lazy[i]);
apply(i<<1|1, lazy[i]);
lazy[i] = T();
}
void update(int tl, int tr, T delta){
update(1, 0, _n - 1, tl, tr, delta);
}
void update(int i, int l, int r, int tl, int tr, T delta){
if (tl <= l && r <= tr){
apply(i, delta);
return;
}
if (tl > r || tr < l) return;
push(i);
int mid = (l + r) >> 1;
update(i<<1, l, mid, tl, tr, delta);
update(i<<1|1, mid+1, r, tl, tr, delta);
tree[i] = merge(tree[i<<1], tree[i<<1|1]);
}
T get(int tl, int tr){
return get(1, 0, _n - 1, tl, tr);
}
T get(int i, int l, int r, int tl, int tr){
if (tl <= l && r <= tr) return tree[i];
if (tl > r || tr < l) return def;
push(i);
int mid = (l + r) >> 1;
T resl = get(i<<1, l, mid, tl, tr);
T resr = get(i<<1|1, mid+1, r, tl, tr);
return merge(resl, resr);
}
};
template <class T = int>
T fmin(T a, T b) { return min(a, b); }
template <class T = int>
T fmax(T a, T b) { return max(a, b); }
Segtree<int, fmin, inf> stmin;
Segtree<int, fmax, -inf> stmax;
int sequence(int N, vector<int> A){
vector<vector<int>> locations(N + 1);
for (int i = 0; i < N; i++) locations[A[i]].push_back(i + 1);
stmin.setup(N + 1);
stmax.setup(N + 1);
for (int i = 1; i <= N; i++) stmin.update(i, N, 1);
for (int i = 1; i <= N; i++) stmax.update(i, N, 1);
auto is_intersect = [&](ii p1, ii p2){
if (p1.first > p2.first) swap(p1, p2);
return p1.second >= p2.first;
};
int ans = 0;
for (int num = 1; num <= N; num++){
if (locations[num].empty()) continue;
for (auto j: locations[num]) stmin.update(j, N, -2);
for (auto j: locations[num]) stmax.update(j, N, -2);
for (int idxl = (int)locations[num].size() - 1; idxl >= 0; idxl--){
int l = locations[num][idxl];
stmin.update(l, N, 2);
stmax.update(l, N, 2);
for (int idxr = idxl + ans; idxr < (int)locations[num].size(); idxr++){
int r = locations[num][idxr];
ii range_lhs = {stmin.get(0, l - 1), stmax.get(0, l - 1)};
ii range_rhs = {stmin.get(r, N) - 2 * (ans + 1), stmax.get(r, N)};
if (is_intersect(range_lhs, range_rhs)){
ans++;
}
else break;
}
}
for (auto j: locations[num]) stmin.update(j, N, -2);
for (auto j: locations[num]) stmax.update(j, N, -2);
}
return ans;
}
#ifdef LOCAL
int main(){
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
cout << "Answer: " << sequence(n, a) << "\n";
}
#endif // LOCAL
