01串

对于相邻的两个段和$S_i$和$S_{i+1}$两段之间移动时的差别既删除了i号元素，添加了i+K号元素。如果$S_i = S_{i+1}+1$那么说明i号元素是1，i+K号元素是0。（删除1添加0）,反之如果$S_i = S_{i+1}-1$，那么i号元素是0，i+K号元素是1(删除1添加0)。这两种情况都能唯一的确定两个位置。

如果$S_i = S_{i+1}$，那么只能说明i号元素和i+K号元素相等，并不能说明其具体的值。我们对这样的元素之间连边，表示相等关系。

那么在构建的图中，一些点已经被确定，一些点没有被确定，但是通过连边关系也能被确定。通过BFS可以求出所有已经确定的点。

接下来，对于前K个元素，我们计算其中还需要补充的1的个数a和尚未确定的位置b，答案既是C(b,a)。从b中任意选a个填1即可。

翻转匹配

分类讨论

对于|T|=1的情况，只需要判断S中是否有对应字符

对于$|T|=2$,$T_1 \neq T_2$的情况，假设T是01，一定是需要把S变成11111...00000...,那么每次操作就需要将一段连续的1移到前面，答案就是连续的1的段的数量$-[S_1=1]$。

对于$|T|=2,T_1=T_2$,假设T是00，那么意味着S中不能出现连续的0。首先通过0的个数是否超过一半判断有解无解。在有解的情况下，任意两个相邻的0都需要一次操作去破坏掉，计算有多少对相邻的0即可。

对于$|T|=3,T_1\neq T_3$,此时如果T多次在S中出现，相互没有交，并且一次操作只能破坏掉一个位置。此时答案是T在S中的出现次数

对于$|T|=3,T_1 \neq T_2$，假设T为010，那么1在不作为前后缀时，长度不能为1。那么一次操作我们可以合并两个长度为1的不作为前后缀的'1'串。答案是$\lceil \frac{段个数}{2} \rceil$

对于$000$的情况，那么不能出现长度大于等于3的0串。首先判断0的个数是否无解(是否大于$\lfloor \frac{n}{3} \rfloor + n$ $mod$ $3$)。

对于一次操作，我们相当于从两个连续段中分别扣除a个0和b个0，再分别添加b个0和a个0(实际上是一个交换的过程)。那么也就是有若干个串允许增加1或者2个0，有若干个串需要减少若干个0。我们希望步骤尽量少，既尽量一次减少两个0。贪心即可。

建筑修缮

称一个数在山谷里，当且仅当在左边和右边都有严格比它大的数。

观察这样一个过程，将所有在山谷里的数的最小值整体+1 。

每次操作 (i,j,k)，$h_j$ 带来的代价是固定的，我们需要尽可能最小化 $h_i,h_k$ 带来的代价。先将这些数中最左边和最右边的数+1 ，然后操作中间的数就可以令 $h_i$和$h_k=h_j+1$ ，非常划算。为了最小化最左边和最右边的数操作的代价，可以算出先左后右，先右后左的代价。这是一个求一段前缀/后缀中某个数后继的问题，可以选用自己喜欢的数据结构维护。

然而h的值域非常大，令x为目前的山谷里的最小值，y为x在所有h_i中的后继，将所有山谷里的最小值从x加到y的过程中，由于需要改变的数的集合不变，可以整体处理，而这个集合只会改变 O(n)次，故复杂度是 O(nlogn)的。

旅行商问题

当K=1时：

交易员必须时刻不停的获取收益，寻找1开始的最长链即可。

当K=2时：

使用树形dp： 设dp1[u]为从u点出发，停在u的子树内的最大价值。 设dp2[u]为从u点出发，停在u的某个儿子或者u本身的最大价值 设dp3[u]为从点u的某个儿子出发，停在u的子树内的最大价值。

那么我们梳理一下具体的构造方式,其中rev()代表把路径反向,v1,v2,...,vk代表u的儿子

方式1：dp1[u]=u->rev(dp2[v1])->v2->...>vk->dp1[vk]

方式2：dp1[u]=u->dp3[v1]

方式3：dp2[u]=u->rev(dp2[v1])->v2->v3->...->vk-1->vk

方式4：dp3[u]=v1->v2->...->dp2[vk-1]->u->dp3[vk]

方式5：dp3[u]=dp2[v1]->u->rev(dp2[v2])->v3->...->vk-1->dp1[vk]

当K=3时

当K=3，交易员可以获取所有的收益，构造方法是：

u->rev(DFS(v1))->rev(DFS(v2))->...rev(DFS(vk))。这样的方式可以遍历所有的点，只需要构造出对应的路径即可。在dfs的过程中标记是否需要反转路径，该标记决定点u是先插入到vector还是后插入到vector即可。

/*
作者也不会做
网上找了份代码 Ctrl+C 了下来
再用 Ctrl+V 大法就过了
还请谅解
另：（也是网上抄的）
    线段树太垃圾了
    大神们可以用平衡树求前驱后继来求 le 和 ri （即左区间（left）和右区间（right）） 
*/ 
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int le[4*N],ri[4*N],f[4*N],cnt[4*N],h[N],n;

//线段树求解左区间 

void pushdown_l(int k){
    if (le[k]==0) return;
    le[k<<1]=max(le[k<<1],le[k]);
    le[k<<1|1]=max(le[k<<1|1],le[k]);
}
void add_l(int k,int l,int r,int L,int R,int v){
    if (r<L||R<l) return; 
    if (L<=l&&r<=R){
        le[k]=max(le[k],v);
        return;
    }
    pushdown_l(k);
    int mid=l+r>>1;
    add_l(k<<1,l,mid,L,R,v);
    add_l(k<<1|1,mid+1,r,L,R,v);
}
int get_l(int k,int l,int r,int p){
    if (l==r){
        return le[k];
    }
    pushdown_l(k);
    int mid=l+r>>1;
    if (p<=mid) return get_l(k<<1,l,mid,p); else return get_l(k<<1|1,mid+1,r,p);
}

//线段树求解右区间 

void pushdown_r(int k){
    if (ri[k]==n+1) return;
    ri[k<<1]=min(ri[k<<1],ri[k]);
    ri[k<<1|1]=min(ri[k<<1|1],ri[k]);
}
void add_r(int k,int l,int r,int L,int R,int v){
    if (r<L||R<l) return;
    if (L<=l&&r<=R){
        ri[k]=min(ri[k],v);
        return;
    }
    pushdown_r(k);
    int mid=l+r>>1;
    add_r(k<<1,l,mid,L,R,v);
    add_r(k<<1|1,mid+1,r,L,R,v);
}
int get_r(int k,int l,int r,int p){
    if (l==r){
        return ri[k];
    }
    pushdown_r(k);
    int mid=l+r>>1;
    if (p<=mid) return get_r(k<<1,l,mid,p); else return get_r(k<<1|1,mid+1,r,p);
}

//用线段树标记不同的 Bessie 值（即 f 数组）（ 1 表示 HI，0 表示 LO，2 表示下辖区块可能 HI，也可能 LO） 

void build(int k,int l,int r){
    if (l==r){
        f[k]=2;
        h[l]=k;//为方便输出，用 h 数组记得 l 的节点值为 k 
        return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    f[k]=2;
}

//更新 k 节点的值为 v 

void count(int k,int v){
    if (v==2) return;
    if (f[k]==1&&v==0){
        f[k]=v;
        cnt[k]++; 
    } else f[k]=v;
}

// f 上放 

void pushup(int k){
    if (f[k<<1]==2||f[k<<1|1]==2){
        f[k]=2;
    } else if (f[k<<1]!=f[k<<1|1]){
        f[k]=2;
    } else if (f[k<<1]==f[k<<1|1]){
        f[k]=f[k<<1];
        f[k<<1]=f[k<<1|1]=2;//当子节点值相同时，防止重复计算，子节点赋值为不确定
    }
}

// f 、懒标记下放 

void pushdown(int k){
    count(k<<1,f[k]);
    cnt[k<<1]+=cnt[k];
    count(k<<1|1,f[k]);
    cnt[k<<1|1]+=cnt[k];
    cnt[k]=0;
}

//更改区间值为 v 

void change(int k,int l,int r,int L,int R,int v){
    if (r<L||R<l) return;
    if (L<=l&&r<=R){
        count(k,v);
        return; 
    }
    pushdown(k);
    int mid=l+r>>1;
    change(k<<1,l,mid,L,R,v);
    change(k<<1|1,mid+1,r,L,R,v);
    pushup(k);
}

//将所有 f 、懒标记的值下放 

void query(int k,int l,int r){
    if (l==r) return;
    pushdown(k);
    int mid=l+r>>1;
    query(k<<1,l,mid);
    query(k<<1|1,mid+1,r);
}



int main(){
    scanf("%d",&n);

    //左右区间初始化 

    for (int i=1;i<=4*n;i++) {
        le[i]=0;
        ri[i]=n+1;
    }
    build(1,0,n);//构造线段树 
    for (int i=1;i<=n;i++){
        int p;
        scanf("%d",&p);
        int x=get_l(1,1,n,p),y=get_r(1,1,n,p);//取出每个值对应的左右区间
        change(1,0,n,x,p-1,1);//对于 left ~ p 标记 HI 
        change(1,0,n,p,y-1,0);//对于 p ~ right 标记 LO 
        add_l(1,1,n,p+1,n,p);//把 p 加入 p 右边的左区间计算中 
        add_r(1,1,n,1,p-1,p);//把 p 加入 p 左边的右区间计算中 
    }
    query(1,0,n);//把所有懒标记下方

    //输出 

    for (int i=0;i<=n;i++)
        printf("%d\n",cnt[h[i]]);
    return 0;
}