题目描述

给你一棵大小为 n 的有根树。结点编号从 1 到 n，根结点编号为 1。 树上每个结点都有一个权值，结点 i 的权值为 $a_{i}$。每个结点的权值各不相同。 对于树上的每个结点 $i(1 ≤i ≤n)$，你需要回答出以它为根的子树中存在多少个结点的权值比它大。即：存在多少个结点 j 满足 j 是 i 的子孙结点且 $a_{j}>a_{i}$。

输入格式

1. 第一行，一个整数 n。
2. 第二行，n 个整数 $a_{1}, a_{2}, ..., a_{n}$，表示每个结点的权值。
3. 接下来 $n-1$ 行，每行包含一个整数，依次表示结点 2、3、...、n 的父结点编号。

输出格式

输出共 n 行，每行包含一个整数。其中第 i 行的整数表示以结点 i 为根的子树中存在多少个结点的权值大于 $a_{i}$。

样例

3
1 2 3
1
1

2
0
0

5
3 5 2 7 11
1
1
2
3

3
1
1
0
0

说明/提示

数据规模与约定

• 对于 20% 的数据，$n ≤10$，$a_{i} ≤10$。
• 对于 50% 的数据，$n ≤1000$，$a_{i} ≤1000$。
• 对于 100% 的数据，$1 ≤n ≤10^{5}$，$1 ≤a_{i} ≤10^{9}$ 且 $a_{i}$ 各不相同，数据保证这是一棵树。