给您一棵$n$个节点的树，树的每个节点上都有一个值$a_i$。现在要您求出从$1$号点到$i$号点的路径上最长上升子序列的长度。

输入格式

第一行一个数$n$，表示节点个数

第二行共$n$个数，第$i$个数表示$a_i$，含义见题面

接下来共有$n-1$行，第两个数$u,v$，表示$u$和$v$之间存在一条边

输出格式

输出共包含$n$行，每行只有一个数，第$i$行的数表示从$1$号点到$i$号点的路径上最长上升子序列的长度。

数据范围：

$2\le n\le 2e5,a_i\le 1e9, u\le n,v\le n,u\neq v$