#include "sequence.h"
#include <bits/extc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int32_t, int32_t>
#define tiii tuple <int32_t, int32_t, int32_t>
#define all(a) a.begin(), a.end()
using namespace std;
using namespace __gnu_pbds;
#define ordered_multiset tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>
const int N = 5e5 + 5;
const int inf = 1e18;
int n, a[N], b[N];
struct lazyseg {
int lazy[4 * N], mnseg[4 * N], mxseg[4 * N];
void push(int l, int r, int i){
mnseg[i] += lazy[i];
mxseg[i] += lazy[i];
if (l != r) lazy[2 * i] += lazy[i], lazy[2 * i + 1] += lazy[i];
lazy[i] = 0;
}
void build(int l, int r, int i){
lazy[i] = 0;
if (l == r) return mnseg[i] = mxseg[i] = b[l], void();
int mid = (l + r) / 2;
build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
mnseg[i] = min(mnseg[2 * i], mnseg[2 * i + 1]);
mxseg[i] = max(mxseg[2 * i], mxseg[2 * i + 1]);
}
void update(int l, int r, int i, int ll, int rr, int val){
push(l, r, i);
if (l >= ll && r <= rr) return lazy[i] += val, push(l, r, i), void();
if (r < ll || l > rr) return;
int mid = (l + r) / 2;
update(l, mid, 2 * i, ll, rr, val);
update(mid + 1, r, 2 * i + 1, ll, rr, val);
mxseg[i] = max(mxseg[2 * i], mxseg[2 * i + 1]);
mnseg[i] = min(mnseg[2 * i], mnseg[2 * i + 1]);
}
int mnquery(int l, int r, int i, int ll, int rr){
push(l, r, i);
if (l >= ll && r <= rr) return mnseg[i];
if (r < ll || l > rr) return inf;
int mid = (l + r) / 2;
return min(mnquery(l, mid, 2 * i, ll, rr), mnquery(mid + 1, r, 2 * i + 1, ll, rr));
}
int mxquery(int l, int r, int i, int ll, int rr){
push(l, r, i);
if (l >= ll && r <= rr) return mxseg[i];
if (r < ll || l > rr) return -inf;
int mid = (l + r) / 2;
return max(mxquery(l, mid, 2 * i, ll, rr), mxquery(mid + 1, r, 2 * i + 1, ll, rr));
}
} neg, pos;
int32_t sequence(int32_t Nn, vector<int32_t> A) {
n = Nn;
vector <vector <int>> mp(n + 1);
for (int i = 0; i < n; i++) {
a[i + 1] = A[i];
b[i + 1] = 1 + b[i];
mp[A[i]].emplace_back(i + 1);
}
int val = 0, ans = 1;
neg.build(1, n, 1);
pos.build(1, n, 1);
for (int i = 1; i <= n; i++) {
auto vec = mp[i];
for (auto idx : vec) neg.update(1, n, 1, idx, n, -2);
for (int j = 0; j < vec.size(); j++) {
int len = ans + 1;
while (j + len - 1 < vec.size()) {
int l = vec[j], r = vec[j + len - 1];
int lmn = min(0ll, pos.mnquery(1, n, 1, 1, l - 1));
int lmx = max(0ll, neg.mxquery(1, n, 1, 1, l - 1));
int rmn = neg.mnquery(1, n, 1, r, n);
int rmx = pos.mxquery(1, n, 1, r, n);
if (rmn - lmx <= 0 && rmx - lmn >= 0) ans++, len++;
else break;
}
}
for (auto idx : vec) pos.update(1, n, 1, idx, n, -2);
}
return ans;
}
