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