Values in a Rooted Tree

Limits: 3 sec., 512 MiB

We have a rooted tree with $n$ vertices. The vertices are numbered $1$ through $n$, and the root is vertex $1$. The $i$-th edge connects vertices $u_i$ and $v_i$. Vertex $v$ has an integer $a_v$ written on it.

For each vertex $v$, find the maximum $m$ such that there exists $x$, such that all values $x, x + 1, \dots, x + m - 1$ are present on the path between the root and vertex $v$.

Input

The first line contains an integer $n$ – the number of vertices in the tree.

The second line contains $n$ integers $a_v$ written on the vertices of the tree.

The following $n - 1$ lines contain two integers $u_i, v_i$ each – the ends of the $i$-th edge.

Output

In a single line, print $n$ integers – the maximum $m$ for each $1 \le v \le n$.

Constraints

$1 \le n \le 3 \cdot 10^5$,

$0 \le a_v \le 10^9$,

$1 \le u_i, v_i \le n$.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 2 4 0 3 5 1 2 1 3 2 4 2 5	1 1 1 3 2

Input (stdin) сopy	Output (stdout) сopy
7 1 3 2 2 0 11 10 4 5 5 1 2 5 2 3 1 6 7 6	1 2 4 3 2 1 2

Notes

In the first example, the answers for all vertices are the following.

• Vertex $1$. Since the root is vertex $1$, thus the path between the root and vertex $1$ contains the only vertex. In this case, $m = 1$.

• Vertex $2$. The path between the root and the vertex $2$ contains two vertices $1$ and $2$ with values $2$ and $4$, respectively. Again, $m = 1$.

• Vertex $3$. The path between the root and the vertex $3$ contains two vertices $1$ and $3$ with values $2$ and $0$, respectively. For vertex $3$, the answer is $m = 1$.

• Vertex $4$. The path between the root and the vertex $4$ contains three vertices $1$, $2$ and $4$ with values $2$, $4$ and $3$ respectively. Here the answer is $m = 3$, because for $x = 2$, the values $x = 2$, $x + 1 = 3$ and $x + 2 = 4$ are present on the path.

• Vertex $5$. The path between the root and the vertex $5$ contains three vertices $1$, $2$ and $5$ with values $2$, $4$ and $5$ respectively. Here, the answer is $m = 2$ because, for $x = 4$, the values $x = 4$ and $x + 1 = 5$ are present on the path.