著名的奥西耶克（Osijek）程序设计训练营非常受欢迎，并扩展到了其他训练营，其中之一就是奥西耶克足球训练营。盛大的奥西耶克足球杯即将开始，因此训练营想要组建一支队伍。但规则非常严格，要求队伍必须恰好由 $k$ 名球员组成。训练营共有 $n$ 名足球运动员，编号从 $1$ 到 $n$。球员们对于他们想和谁一起加入队伍有自己的偏好。球员 $i$ 的偏好形式如下： “如果我加入队伍，那么球员 $a_i$ 也必须加入队伍。” 可能存在 $i = a_i$ 的情况；这意味着该球员只关心他们自己。

此外，球员们还有一个额外的要求： “我不希望和那些没有通过偏好链与我相连的人在同一个队伍里。” 偏好链是一个球员序列 $u, p_2, p_3, p_4, \dots, v$，使得序列中的下一个球员是当前球员的 $a_i$。如果存在从 $u$ 到 $v$ 或从 $v$ 到 $u$ 的偏好链，则称球员 $u$ 和 $v$ 是相连的。

不幸的是，在仔细阅读规则后，$k$ 的值仍然不明确。因此，对于从 $1$ 到 $n$ 的所有 $k$，你都需要考虑需要组建一支大小为 $k$ 的队伍的情况。如果无法组建队伍，你决定与球员们交谈。在一次会议中，你可以选择一名球员 $i$，并说服他们改变偏好。形式上，你可以选择 $1 \le i, x \le n$ 并执行更新 $a_i := x$。在此之后，允许 $a_i = i$。

对于每个从 $1$ 到 $n$ 的 $k$，求出你需要组建一支大小为 $k$ 的队伍所需的最少会议次数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500\,000$)，表示奥西耶克足球训练营的球员人数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示所有球员当前的偏好。

输出格式

输出一行，包含 $n$ 个整数，表示对于所有从 $1$ 到 $n$ 的 $k$，组建队伍所需的最少会议次数。

样例

输入 1

5
2 3 1 3 5

输出 1

0 1 0 0 1