当 Adam 得到一棵有根树(无环的连通无向图)时,他立即开始为其着色。更正式地说,他为树的每条边分配一种颜色,使其满足以下两个条件:
- 没有顶点有两个以上的入射边被涂成相同的颜色。
- 对于具有相同颜色(例如,c)的入射边的任何两个顶点,它们之间的路径由颜色 c 的边组成。
并非所有的树画都同样适合亚当。让我们考虑从某个顶点到根的路径。我们将该路径上不同颜色的数量称为顶点的成本。树的着色成本将是所有顶点中最大的成本。帮助亚当确定画树的最低可能成本。
最初,亚当树由单个顶点组成,该顶点的编号为 1,并且是根。 Adam 在一次移动中向已有的顶点添加了一个新顶点,新顶点的数字等于可用的最小正整数。每次操作后,您需要计算为结果树着色的最小成本。
输入
第一行包含整数 n (1 ≤ n ≤ 106) — 添加新顶点的次数。第二行包含 n 个数字 pi (1 ≤ pi ≤ i) — 我们添加另一个顶点的顶点的编号。
输出
打印 n 个整数 — 每次相加后树绘制的最小成本。
示例
输入 #1
11 1 1 1 3 4 4 7 3 7 6 6
输出 #1
1 1 1 1 1 2 2 2 2 2 3
注意
下图显示了在最后一刻根据样本绘制树的可能变体之一。编号为 11 和 12 的顶点的成本等于 3。