#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
pair<int ,int> comb(pair<int ,int> a , pair<int ,int> b)
{
return {min(a.first , b.first) , max(a.second , b.second)};
}
struct segTree
{
int BASE;
vector<pair<int ,int>> tree;
vector<int> tag;
void init(int n)
{
BASE = n;
while(__builtin_popcount(BASE) != 1)
BASE++;
tag.assign(2*BASE , 0);
tree.assign(2*BASE , {BASE , -BASE});
for(int i = 0 ; i < n ; i++)
{
tree[i + BASE] = {i , i};
}
for(int i = BASE - 1 ; i >= 1 ; i--)
{
tree[i] = comb(tree[i<<1] , tree[i<<1|1]);
}
}
void add(int node , int s , int e , int l , int r , int val)
{
if(s > r || l > e)
return;
if(l <= s && e <= r)
{
tree[node].first+=val;
tree[node].second+=val;
tag[node]+=val;
return ;
}
int m = (s + e)>>1;
add(node<<1 , s , m , l , r , val);
add(node<<1|1 , m + 1 , e , l , r , val);
tree[node] = comb(tree[node<<1] , tree[node<<1|1]);
tree[node].first+=tag[node];
tree[node].second+=tag[node];
}
void add(int l , int r , int val)
{
add(1 , 0 , BASE - 1 , l , r , val);
}
pair<int, int> query(int node ,int s , int e ,int l, int r) {
if (l > e || s > r) {
return {BASE , -BASE};
}
if (l <= s && e <= r) {
return tree[node];
}
int mid = (s + e) >> 1;
pair<int, int> res = comb(query(node << 1, s, mid, l, r) , query(node << 1|1, mid + 1, e, l, r));
res.first += tag[node], res.second += tag[node];
return res;
}
pair<int ,int> query(int l , int r)
{
return query(1 , 0 , BASE - 1 , l , r);
}
}tree;
bool check(int i , int j , int w , int N)
{
auto rt = tree.query(j + 1 , N);
rt.first-=2*w;
auto lt = tree.query(0, i);
return (max(rt.first , lt.first) <= min(lt.second , rt.second));
}
int sequence(int N, std::vector<int> A)
{
vector<int> occ[N];
tree.init(N + 1);
for(int i = 0 ; i < N ; i++)
{
A[i]--;
occ[A[i]].push_back(i);
}
int ans = 1;
for(int cur = 0 ; cur <N ; cur--)
{
for(int i = 0 ; i < (int)occ[cur].size() ; i++)
{
tree.add(occ[cur][i] + 1 , N , -2);
}
for(int i = (int)occ[cur].size() - 1 ; i >= 0 ; i--)
{
tree.add(occ[cur][i] + 1 , N , 2);
while(ans + i < (int)occ[cur].size() && (check(occ[cur][i] , occ[cur][ans + i] , ans + 1 , N)))
{
ans++;
}
}
for(int i : occ[cur])
tree.add(i + 1 , N , -2);
}
return ans;
}
