Arkady的话在一家大公司。有n名员工在一个严格的等级制度中工作。也就是说,除首席执行官外,每位员工都只有一名直属经理。首席执行官是所有员工的管理者(通过一系列直属管理者)。
每个员工都有一个整数等级。 CEO 的级别等于 1,其他员工的级别等于其直属经理的级别加 1。
Arkady在公司的职位很好,但他觉得自己在公司的架构中无足轻重,可以替代他的人还有很多。他介绍了可替代性的价值。考虑员工 a 和员工 b,后者是 a 的经理(不一定是直接经理)。那么a相对于b的可替代性r(a,b)就是经理b的级别不大于a级别的下属(不一定是直属)的数量。除了可替代性之外,阿尔卡迪还引入了可忽略性的价值。员工 a 的可忽略性 za 等于他相对于所有经理的可替代性之和,即 $$z_{a} = \sum_{b} r(a,b)$$,其中该总和被接管到他的所有经理 b 上。
阿尔卡迪不仅对自己的忽视感兴趣,而且对公司所有员工的忽视感兴趣。求每个员工对于Arkady 的可忽略性。
输入
第一行包含单个整数 n (1 ≤ n ≤ 5·105) — 公司的员工人数。
第二行包含 n 个整数 p1, p2, ..., pn (0 ≤ pi ≤ n),其中如果第 i 个员工是 CEO,则 pi = 0,否则 pi 等于 ID 为 i 的员工的直属经理的 ID。员工编号从 1 到 n。可以保证这些值中恰好有一个 0,并且 CEO 是所有其他员工的经理(不一定是直属经理)。
输出
打印 n 个整数 — 按 ID 顺序排列的所有员工的可忽略性:z1、z2、...、zn。
示例
输入 #1
4 0 1 2 1
输出 #1
0 2 4 2
输入 #2
5 2 3 4 5 0
输出 #2
10 6 3 1 0
输入 #3
5 0 1 1 1 3
输出 #3
0 3 3 3 5
注意
考虑第一个例子:
- CEO 没有经理,因此 z1 = 0。
- r(2, 1) = 2(员工2和4符合条件,员工3的级别太大)。因此z2 = r(2, 1) = 2。
- 同样,z4 = r(4, 1) = 2。
- r(3, 2) = 1(员工3是2的下属,具有合适的级别)。 r(3, 1) = 3(员工2、3、4符合条件)。因此z3 = r(3, 2) + r(3, 1) = 4。