We have a tree with n vertices, whose i-th edge connects Vertex ui and Vertex vi. Vertex i has an integer ai written on it. For every integer k from 1 through n, solve the following problem:

We will make a sequence by lining up the integers written on the vertices along the shortest path from Vertex 1 to Vertex k, in the order they appear. Find the length of the longest increasing subsequence of this sequence.

Here, the longest increasing subsequence of a sequence A of length L is the subsequence Ai1, Ai2, ..., Aim with the greatest possible value of m such that 1 ≤ i1 < i2 < ...< im ≤ L and Ai1 < Ai2 < ... < Aim.

Input

The first line contains number n (2 ≤ n ≤ 2 * 105). The second line contains numbers a1, a2, ..., an (1 ≤ ai ≤ 109). Each of the next n - 1 lines contains an edge (ui, vi) (1 ≤ ui, vi ≤ n).

Output

Print n lines. In the k-th line, print the length of the longest increasing subsequence of the sequence obtained from the shortest path from Vertex 1 to Vertex k.