Cho một cây có trọng số gồm ~n~ đỉnh, được đánh số từ ~1~ đến ~n~, trọng số của đỉnh thứ ~i~ là ~a_i~. Gọi ~S(i)~ là dãy các trọng số của các đỉnh trên đường đi từ ~1~ tới ~i~.

Với mỗi ~i~, hãy tìm độ dài dãy con tăng dài nhất của ~S(i)~.

Input

• Dòng đầu chứa số nguyên ~n~ ~(n \le 2 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ miêu tả trọng số của các đỉnh ~(1 \le a_i \le 10^9)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1≤u,v≤n; u≠v)~ mô tả một cạnh của cây nối hai đỉnh ~u~ và ~v~.

Output

• In ra ~n~ số nguyên là độ dài của dãy con tăng dài nhất của ~S(i)~.

Subtask

• Subtask ~1~: ~a_i \le 100~. ~(30\%)~
• Subtask ~2~: Không có đỉnh nào có quá hai cạnh nối. ~(30\%)~
• Subtask ~3~: Không có ràng buộc gì thêm. ~(40\%)~

Sample Input 1

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

Sample Output 1

1
2
3
3
4
4
5
2
2
3