#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int sum , pfmax , pfmin;
};
Node comb(Node a , Node b)
{
Node ans;
ans.sum = a.sum + b.sum;
ans.pfmax = max(a.sum + b.pfmax , a.pfmax);
ans.pfmin = min(a.sum + b.pfmin , a.pfmin);
return ans;
}
struct segTree
{
int BASE;
vector<Node> tree;
void init(int n)
{
BASE = n;
while(__builtin_popcount(BASE) != 1)
BASE++;
tree.assign(2*BASE , {0 , 0 , 0});
for(int i = 0 ; i < n ; i++)
{
tree[i + BASE] = {-1 , -1 , -1};
}
for(int i = BASE - 1 ; i >= 1 ; i--)
{
tree[i] = comb(tree[i<<1] , tree[i<<1|1]);
}
}
void upd(int i , int x)
{
tree[i + BASE] = {x , x , x};
for(int j = (i + BASE) / 2 ; j >= 1 ; j>>=1)
{
tree[j] = comb(tree[j<<1] , tree[j<<1|1]);
}
}
Node query(int l , int r)
{
if(r == -1)
{
return {0 , 0 , 0};
}
l+=BASE;
r+=BASE;
if(l == r)
return tree[l];
Node lt = tree[l], rt = tree[r];
while(l + 1 < r)
{
if(l%2 == 0)
{
lt = comb(lt , tree[l + 1]);
}
if(r%2 == 1)
{
rt = comb(tree[r - 1] , rt);
}
l>>=1;
r>>=1;
}
return comb(lt , rt);
}
}tree;
bool check(int i , int j , int w , int N)
{
auto rt = tree.query(j , N - 1);
int tot = tree.query(0 , j - 1).sum;
int mxj = rt.pfmax + tot;
int mnj = rt.pfmin + tot;
auto lt = tree.query(0 , i - 1);
int mxi = lt.pfmax;
mxi = max(mxi , 0);
int mni = lt.pfmin;
mni = min(mni , 0);
int mx = mxj - mni;
int mn = mnj - mxi;
if(mn <= 0 && mx >= 0)
{
return 1;
}
else if(mn > 0)
{
if(w >= mn)
return 1;
return 0;
}
else
{
if(w >= abs(mx))
{
return 1;
}
return 0;
}
return 0;
}
int sequence(int N, std::vector<int> A)
{
vector<int> occ[N + 1];
tree.init(N);
for(int i = 0 ; i < N ; i++)
{
A[i]--;
occ[A[i]].push_back(i);
}
int ans = 1;
for(int cur = N - 1 ; cur >= 0 ; cur--)
{
for(int i = 0 ; i < (int)occ[cur + 1].size() ; i++)
{
tree.upd(occ[cur + 1][i], 1);
}
for(int i = 0 ; i < (int)occ[cur].size() ; i++)
{
tree.upd(occ[cur][i] , 0);
}
for(int i = (int)occ[cur].size() - 1 ; i >= 0 ; i--)
{
while(ans + i < (int)occ[cur].size() && check(occ[cur][i] , occ[cur][ans + i] , ans + 1 , N))
{
ans++;
}
}
}
return ans;
}
