There are $N$ cities in JOI Kingdom, which are indexed by the numbers from $1$ to $N$. City $1$ is the capital city. Each city has a value called liveliness and the initial value of liveliness of city $i$ $(1\le i\le N)$ is $C_i$. Roads in JOI Kingdom connect two different cities bidirectionally. Initially, there are no roads in JOI Kingdom. You have planned $N-1$ constructions of roads. The $j$-th construction $(1\le j\le N-1)$ is planned to be done in the following way.

• Two cities, $A_j$ and $B_j$, are appointed, when one can go from city $1$ to city $A_j$ and cannot go from city $1$ to city $B_j$ by using only roads constructed at that time.
• You construct a road connecting city $A_j$ and city $B_j$. The cost of this construction is the number of pairs of cities $(s,t)$ satisfying the following conditions: City $s$ and City $t$ lie on the shortest path between city $1$ and city $A_j$, and when one goes from city $1$ to city $A_j$ he arrives city $s$ before city $t$, and the value of liveliness of city $s$ is strictly larger than that of city $t$. Here, cities lying on the path between city $1$ and city $A_j$ include city $1$ and city $A_j$. Notice that the shortest path between city $1$ and city $A_j$ is unique.
• The values of liveliness of all cities lying on the path between city $1$ and city $A_j$ change to the value of liveliness of city $B_j$.

You want to know the cost of each construction.

Input Specification

The first line of input contains an integer $N$. This means there are $N$ cities in JOI Kingdom.

The second line of input contains $N$ space separated integers $C_i$. This means the initial value of liveliness of city $i$ is $C_i$.

Each of following $N-1$ lines contains two space separated integers $A_j$, $B_j$. This means city $A_j$ and city $B_j$ are appointed for the $j$-th construction of road. By using roads constructed before the $j$-th construction, one can go from city $1$ to city $A_j$ and cannot go from city $1$ to city $B_j$ $(1\le j\le N-1)$.

Output Specification

Output $N-1$ lines to the standard output. The $j$-th line $(1\le j\le N-1)$ of output contains the cost of the $j$-th construction of road.

Constraints

All input data satisfy the following conditions.

• $1\le N\le {10}^5$
• $1\le C_i\le {10}^9$ $(1\le i\le N)$
• $1\le A_j\le N$ $(1\le j\le N-1)$
• $1\le B_j\le N$ $(1\le j\le N-1)$
• By using roads constructed before the $j$-th construction, one can go from city $1$ to city $A_j$ and cannot go from city $1$ to city $B_j$ $(1\le j\le N-1)$.

Subtask	Points	Additional constraints
$1$	$7$	$N\le 500$
$2$	$9$	$N\le 4000$
$3$	$84$	$N\le {10}^5$

Sample Input 1

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

Sample Output 1

0
0
0
2

Explanation for Sample 1

In Sample Input 1, constructions are done as follows:

• In the first construction, there are no pairs $(s,t)$ satisfying the conditions, so the cost is 0. A road connecting city 1 and city 2 is constructed and the value of liveliness of city 1 changes to 2.
• In the second construction, there are no pairs $(s,t)$ satisfying the conditions too, so the cost is 0. A road connecting city 2 and city 3 is constructed and the values of liveliness of city 1 and city 2 change to 3.
• In the third construction, there are no pairs $(s,t)$ satisfying the conditions too, so the cost is 0. A road connecting city 2 and city 4 is constructed and the values of liveliness of city 1 and city 2 change to 4.
• In the fourth construction, two pairs $(s,t)=(1,3),(2,3)$ satisfy the conditions, so the cost is 2. A road connecting city 3 and city 5 is constructed and the values of liveliness of city 1, city 2 and city 3 change to 5.

Sample Input 2

10
1 7 3 4 8 6 2 9 10 5
1 2
1 3
2 4
3 5
2 6
3 7
4 8
5 9
6 10

Sample Output 2

0
0
0
1
1
0
1
2
3