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.