#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
struct T{
int Minpre=0,Maxpre=0,Minsuf=0,Maxsuf=0,sum=0;
};
T TT(T &le,T &ri){
T pa;
pa.sum=le.sum+ri.sum;
pa.Minpre=min(le.Minpre,le.sum+ri.Minpre);
pa.Maxpre=max(le.Maxpre,le.sum+ri.Maxpre);
pa.Minsuf=min(ri.Minsuf,le.Minsuf+ri.sum);
pa.Maxsuf=max(ri.Maxsuf,le.Maxsuf+ri.sum);
return pa;
}
T Tid;
struct segtree{
vector<T> seg;
int n,lg;
void refresh(int v){
seg[v]=TT(seg[v<<1],seg[(v<<1)|1]);
}
void build(int siz){
n=1;
while(n<siz){
n<<=1;
}
lg=__lg(n);
seg.assign(n<<1,Tid);
}
void update(int l,int x){
l+=n;
seg[l].sum=x;
seg[l].Minpre=min(0,x),seg[l].Maxpre=max(0,x);
seg[l].Minsuf=seg[l].Minpre,seg[l].Maxsuf=seg[l].Maxpre;
for(int i=1;i<=lg;i++){
refresh(l>>i);
}
}
T query(int l,int r){
T le=Tid,ri=Tid;
for(;l<r;l>>=1,r>>=1){
if(l&1){
le=TT(le,seg[l]);
l++;
}
if(r&1){
r--;
ri=TT(seg[r],ri);
}
}
return TT(le,ri);
}
};
struct fenwick{
vector<int> bit;
void build(int siz){
bit.resize(siz+1);
for(int i=1;i<=siz;i++){
bit[i]=1e9;
}
}
void update(int i,int x){
for(;i<bit.size();i+=(i&(-i))){
bit[i]=min(bit[i],x);
}
}
int query(int i){
int curr=1e9;
for(;i;i-=(i&(-i))){
curr=min(curr,bit[i]);
}
return curr;
}
};
int sequence(int n,vector<int> a){
segtree seg;
vector<vector<int>> occu(n+1);
for(int i=0;i<n;i++){
occu[a[i]].push_back(i);
}
seg.build(n);
for(int i=0;i<n;i++){
if(a[i]>1){
seg.update(i,-1);
}
}
for(int x=1;x<=n;x++){
}
}
