题目背景

在一片神秘的森林，里面有 $N$ 个古老的树屋，每个树屋上都刻着一个独特的数字 $a_i$。这些树屋通过 $N-1$ 条吊桥连接，形成了一张巨大的树形网络，没有任何环路，保证每个树屋都可以通过吊桥到达。森林的入口是树屋 $1$，每个吊桥连接着两个树屋 $u_i$ 和 $v_i$。现在，你是一个勇敢的探险家，从入口树屋 $1$ 开始，沿着吊桥前往每个树屋 $k$（从 $1$ 到 $N$）。在探险过程中，你会记录下沿途经过的树屋上刻着的数字，按照从 $1$ 到 $k$ 的最短路径顺序，组成一个数字序列。

对于每一个目标树屋 $k$，找到这个数字序列中最长的上升子序列的长度。所谓“最长上升子序列”，就是从序列中挑出一些数字，组成一个新的子序列 $A_{i_1}, A_{i_2}, ..., A_{i_M}$，要求这些数字严格递增（即 $A_{i_1} < A_{i_2} < ... < A_{i_M}$），并且位置按照原序列的顺序（即 $1 \leq i_1 < i_2 < ... < i_M \leq L$，其中 $L$ 是序列长度），使得这个子序列的长度 $M$ 尽可能大。

输入格式

• 第一行：一个整数 $N$，表示树屋数量。
• 第二行：$N$ 个整数 $a_1, a_2, ..., a_N$，表示每个树屋上刻的数字。
• 接下来 $N-1$ 行：每行两个整数 $u_i, v_i$，表示一条吊桥连接树屋 $u_i$ 和树屋 $v_i$。

输出格式

输出 $N$ 行，第 $k$ 行表示从树屋 $1$ 到树屋 $k$ 的最短路径上形成的数字序列的最长上升子序列的长度。

数据范围

• $2 \leq N \leq 2 \times 10^5$（树屋数量在 2 到 200,000 之间）
• $1 \leq a_i \leq 10^9$（每个树屋上的数字是 1 到 $10^9$ 之间的整数）
• $1 \leq u_i, v_i \leq N$（吊桥连接的树屋编号在合法范围内）
• $u_i \neq v_i$（吊桥不会连接同一个树屋）
• 给定的吊桥网络是一棵树（无环，保证连通）
• 输入的所有值均为整数

样例

10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10

1
2
3
3
4
4
5
2
2
3

样例说明

以从树屋 $1$ 到树屋 $5$ 的路径为例：

• 最短路径是 $1 \to 2 \to 3 \to 4 \to 5$，
• 沿途数字序列为 $1, 2, 5, 3, 4$，
• 其中最长的上升子序列是 $1, 2, 3, 4$（对应位置 $A_1, A_2, A_4, A_5$），长度为 $4$。 因此，第 5 行的输出是 $4$。