#P18501. Football in Osijek

Football in Osijek

Football in Osijek

著名的 Osijek 竞赛训练营越来越受欢迎,还开设了其它训练营,其中包括 Osijek 足球训练营。Osijek 足球杯即将举行,训练营希望组建一支队伍,但规则严格要求队伍恰好包含 kk 名球员。

训练营有 nn 名球员,编号为 1,2,…,n1,2,\ldots,n。球员 ii 的偏好是:

如果我加入队伍,球员 aia_i 也必须加入。

允许 ai=ia_i=i,这表示该球员只关心自己。

此外,每名球员还有一个要求:

我不想与和我之间没有偏好链联系的人在同一支队伍。

偏好链是一个球员序列 u,p2,p3,…,vu,p_2,p_3,\ldots,v,其中每一步的下一个球员都是当前球员偏好指向的球员,即从当前球员 xx 走向 axa_x。两名球员 u,vu,v 有联系,当且仅当存在一条从 uu 到 vv 的偏好链,或者存在一条从 vv 到 uu 的偏好链。

换言之,合法队伍既要满足所有入队球员的偏好闭包,又要满足队伍中任意两名球员至少在上述一个方向上可达;这里只看无向连通不足以满足要求。

遗憾的是,规则中的 kk 尚未确定。你需要分别考虑 k=1,2,…,nk=1,2,\ldots,n 的所有情况:如果原来无法组建这样的队伍,可以与球员会面,劝说其修改偏好。

一次会面可以任选 1≤i,x≤n1\le i,x\le n,将 aia_i 改为 xx。修改后仍允许 ai=ia_i=i。

对于每个 k=1,2,…,nk=1,2,\ldots,n,求为了能够组建一支恰有 kk 人的合法队伍,最少需要多少次会面。各个 kk 的场景相互独立,都从输入给出的原偏好开始考虑。

输入格式

第一行一个整数 nn(1≤n≤500 0001\le n\le 500\,000),表示球员人数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(1≤ai≤n1\le a_i\le n),表示原来的偏好。

输出格式

输出一行 nn 个整数,第 kk 个整数表示组建恰好 kk 人的合法队伍所需的最少会面次数。

完整原样例

5
2 3 1 3 5
0 1 0 0 1