背景

夏夜的市集开张了。主办方把一整套串灯从电源出发一层层地分叉：一个插座接两个分线器，分线器再接新的分线器或灯串……所有连接形成了一张从电源开始、每个插头只有一个上游的层级网络。

为了布置不同风格的区域，工作人员会做一种“温柔的改造”—— 一次操作：选定一个分线器（或插头），把它与所有直接下游插头的连线一起拔掉。被拔掉的一端不会再连回去；上游部分仍保持原样。这样一来，下面的每一支线都会变成一个独立的灯串小群。

我们想知道：对每一个目标值 $k \in [1,n]$（$n$ 为插头/分线器/灯串的总数，电源记为 1 号），最少需要做几次这样的操作，才能让全场恰好分成 $k$ 个彼此独立、互不相连的灯串群？如果无论怎么拔都做不到，就输出 $-1$。

题目要求

输入格式

• 第一行：一个正整数 $n$（灯串网络的节点数，电源为 1 号）。

• 第二行：$n-1$ 个整数 $f_i$（$1 \le f_i \le i$），表示 $i+1$ 号插头/分线器的上游是 $f_i$。

  也就是从 1 号电源出发的“家谱式”接线；保证没有环。

输出格式

输出 $n$ 个整数，第 $i$ 个数表示当目标为 $k=i$ 时需要的最少操作次数；若无法做到，输出 $-1$。

样例

输入

6
1 2 1 1 2

输出

0 -1 1 1 -1 2

解释 此网络中：1 号有 3 个直接下游，2 号有 2 个直接下游，其余为末端。

• 想分成 1 组：不用动（0 次）。
• 想分成 3 组：拔 2 号一次即可（+2 条连线 → 3 组）。
• 想分成 4 组：拔 1 号一次即可（+3 条连线 → 4 组）。
• 想分成 6 组：拔 1 号和 2 号各一次（+5 条连线 → 6 组）。
• 分成 2 或 5 组做不到（因为“+1”或“+4”无从凑出）。

数据范围与测试

共 10 个测试点。

• 子任务 A（30 分）：$1 \le n \le 20$
• 子任务 B（30 分）：$1 \le n \le 100$
• 子任务 C（40 分）：$1 \le n \le 3000$