You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

成功多在困苦时

败事起于忘形日

你要我跟你说几次

达官贵人要淡泊明志

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

题目描述

小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$。