Background

小埋通过使用瑞克的传送枪，来到了不同时空小埋聚集的地方。众所周知，小埋在本宇宙是“完美”的，可是在这里，小埋见到了比她更完美的人，当然，也存在比她差的小埋。同时，这个聚集地为管理不同宇宙小埋也有着上下级的关系。

Description

有 $n$ 个小埋，每个小埋有个完美值 $ai$（保证每个 $ai$ 不同），同时她们的上下级关系形成一个树形结构，小埋发现有许多上级的完美值小于下级，因此小埋想改善这种关系，所以，你现在要告诉小埋对每个 $i$，有多少个下级小埋的完美值 $aj>ai$（j在i的子树中）。

Input

第一行 $n（1<=n<=1e5）$，表示树形结构中小埋的数量 接下来 $n$ 行是每个小埋的完美值 $ai(1<=ai<=1e9)$，保证互不相同 接下来 $n-1$ 行描述为小埋 $2$~$n$的直接负责上级， $1$ 号小埋没有上司。

Output

输出 $n$ 行，第 $i$ 行表示 $i$ 号小埋的所有下级（$i$节点的子树）完美值大于 $i$ 号小埋的数量

Samples

input1

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3

output1

2
0
1
0
0

Limitation

1s, 256MB