1472: Stable Company

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:127 Solved:21

Description

一个公司的人员组成结构可以用一个有根树来表示,职位较高的人在树形结构中处于深度较低,靠近根节点的位置,而刚入职的员工则可能处于树的叶子节点的位置。每个人都有一个能力值,能力值越高代表这个员工的个人能力较强,理应在职位较高的位置,但在现实生活中,往往出现‘才不配位’的情况。为了维持公司的稳定,往往需要尽可能的让一个员工的能力值比他手下其他员工的能力值都要高。

      假设给员工顺序标号1~N,现在人事部给出每个员工的能力值和公司的人员组成结构树形图,需要你给出每个员工的所有下属(直接和间接下属)中有多少人能力值大于他。

    简化题意:问每个结点的子树中有多少个结点的能力值比他大。

Input

第一行一个整数N,表示公司员工数

第二行N个整数,表示员工的能力值pi

接下来N-1行,每行一个整数,表示编号2~N的员工的直接上属,1号员工为最高领导。

Output

N行,每行一个整数表示编号为i的员工的下属中有几个能力值比i大的。

Sample Input Copy

5
3 4 1 2 5
1
1
2
3

Sample Output Copy

2
0
1
0
0

HINT

1≤N≤100,000,1≤pi≤100,000