题目描述

一家公司的员工从 $1\sim n$ 编号,组织架构是一棵树:$1$ 号员工是总经理(树根),其余每名员工都恰好有一名直接上司(树上的父亲节点)。

每名员工 $i$ 都有一个能力指数 $p_i$,所有员工的能力指数互不相同。如果员工 $i$ 是员工 $j$ 的祖先节点,那么员工 $j$ 就是 $i$ 的下属。

管理层发现,时常会出现上司的能力指数比某些下属还低的情况,这时上司应当考虑晋升这些下属。请你帮助管理层统计:对于每一名员工 $i$,其下属中满足 $p_j \gt p_i$ 的员工 $j$ 的数量。

输入格式

输入的第一行包括一个整数 $n$。

接下来的 $n$ 行包括员工的能力指数 $p_1,p_2,\dots,p_n$,保证所有数互不相同。

接下来的 $n-1$ 行依次描述员工 $2 \sim n$ 的上司编号($1$ 号员工是总经理,没有上司)。

输出格式

输出包括 $n$ 行,第 $i$ 行给出一个整数:员工 $i$ 的下属中能力指数比 $i$ 高的人数。

样例

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3

2
0
1
0
0

提示

对于 $100\%$ 的数据,$1\le n \le 10^5$,$1 \le p_i \le 10^9$。