题目背景

成功多在困苦时

败事起于忘形日

你要我跟你说几次

达官贵人要淡泊明志

想干出一番光宗耀祖的事业，可没那么容易。

题目描述

小s家是一个大家庭，这个家庭的族谱关系错综复杂，但是可以用一棵树来表示。

由于古时候重男轻女的思想，这张族谱上只写了所有男性。

$1$ 是所有人的祖先。

每个人都有自己的贡献值，表明他为这个家族的繁荣做出的贡献是多少。

现在小s想问你，对于族谱上的每一个人 $x$，$x$ 记在族谱上的祖先中有多少人所做的贡献没有 $x$ 的大，即贡献值严格小于 $x$（如果存在这样的祖先，我们就说 $x$ 实现了“光宗耀祖”）。

注意，此题中 $x$ 的祖先，只计算 $x$ 的父亲，爷爷，爷爷的父亲，爷爷的爷爷等节点。

输入格式

第一行一个整数 $n$，表示人数。

第二行 $n$ 个整数，第 $i$ 个数表示第 $i$ 个人的贡献值。

第 $3$ 行开始有 $n-1$ 行，每行两个整数 $x,y$，表示 $x$ 和 $y$ 是相邻一代，可能是 $x$ 生了 $y$，也可能是 $y$ 生了 $x$。

输出格式

$n$ 行，第 $i$ 行一个整数，表示 $i$ 的祖先中有多少人做出的贡献没有 $i$ 大。

5
3 2 4 1 3
1 2
1 3
2 4
2 5

0
0
1
0
1

数据解释

1 号节点，祖先构成的集合为 $\{\}$，没有节点满足条件。

2号节点，祖先构成的集合为 $\{1\}$，没有节点满足条件。

3号节点，祖先构成的集合为 $\{1\}$，其中 $1$ 节点贡献值小于 $3$ 节点贡献值。

4号节点，祖先构成的集合为 $\{1,2\}$，没有节点满足条件。

5号节点，祖先构成的集合为 $\{1,2\}$，其中 $2$ 节点贡献值小于 $5$ 节点贡献值。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,a_i \le 10^6$。