Cho một cây vô hướng không trọng số gồm ~n~ đỉnh, đỉnh thứ ~i~ có trọng số là ~a_i~.

Với mỗi đỉnh ~u~, hãy xác định xem có bao nhiêu đỉnh ~v~ là tổ tiên của ~u~ thỏa mãn ~a_v~ > ~a_u~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên, số thứ ~i~ miêu tả giá trị ~a_i~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~x,y~ miêu tả cạnh của cây.

Constraint

• ~1 \le n\le 10^5~
• ~1 \le a_i \le 10^9~

Subtask

• Subtask ~1~ ~(40\%)~: ~n \le 2000~.
• Subtaks ~2~ ~(60\%)~: Không có điều kiện gì thêm.

Output

• Gồm ~n~ số nguyên trên một dòng, số thứ ~i~ là kết quả của đỉnh thứ ~i~.

Sample Input 1:

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

Sample Output 1:

0 1 0 2 1