Description

The squirrel’s new home is a tree. It was just renovated a few days ago. The new home has $n$ rooms and $n-1$ edges connecting them. Every pair of rooms is reachable, and the route between any two rooms is unique. Oh my, he really lives on a "tree".

The squirrel wants to invite Winnie the Pooh to visit and specifies a visiting itinerary. He hopes Winnie will visit in order: first $a_1$, then $a_2$, …, and finally $a_n$. However, this would cause revisiting many rooms, and the lazy Winnie keeps refusing. But the squirrel tells him that each time he arrives at a room, he can take one candy from that room.

Winnie is a glutton, so he agrees at once. Now the squirrel wants to know, to ensure Winnie always has a candy to eat, how many candies at minimum he needs to place in each room.

Since the last room $a_n$ in the itinerary is the dining room, where a feast has been prepared, when Winnie arrives at the dining room at the end of the tour, he does not need to take a candy there.

Input Format

The first line contains a positive integer $n$, the number of rooms. The second line contains $n$ positive integers describing $a_1, a_2, \cdots, a_n$ in order.

The next $n-1$ lines each contain two positive integers $x, y$, indicating that rooms labeled $x$ and $y$ are connected by an edge.

Output Format

Output $n$ lines. On the $i$-th line, output the minimum number of candies that must be placed in the room labeled $i$ so that Winnie always has a candy to eat.

5
1 4 5 3 2
1 2
2 4
2 3
4 5

1
2
1
2
1

Hint

For all testdata, $2 \le n \le 3 \times 10^5$, $1 \le a_i \le n$.

Translated by ChatGPT 5