Chuyến lưu diễn

Treeland có $n$ thành phố, được nối với nhau bởi $n-1$ con đường hai chiều sao cho từ một thành phố bất kỳ đều có thể đi tới mọi thành phố còn lại. Thành phố thứ $i$ có dân số $r_i$.

Một ban nhạc sẽ thực hiện chuyến lưu diễn dọc theo một đường đi đơn: họ xuất phát từ một thành phố nào đó và di chuyển liên tiếp sang các thành phố kề, không bao giờ quay lại thành phố đã đi qua. Trên đường đi đó, ban nhạc sẽ tổ chức hoà nhạc tại một số thành phố (không nhất thiết là tất cả), theo đúng thứ tự các thành phố được đi qua.

Ban nhạc chỉ nhận biểu diễn ở nơi ngày càng lớn: mỗi buổi hoà nhạc phải được tổ chức tại thành phố có dân số lớn hơn thành phố của buổi hoà nhạc liền trước. Nói cách khác, dãy dân số của các thành phố tổ chức hoà nhạc, xét theo thứ tự đi qua, phải tăng ngặt.

Hãy tìm số buổi hoà nhạc lớn nhất mà ban nhạc có thể tổ chức.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số thành phố.
• Dòng thứ hai chứa $n$ số nguyên $r_1,r_2,\dots ,r_n$ là dân số của các thành phố.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_j,b_j$ mô tả một con đường nối hai thành phố $a_j$ và $b_j$.

Dữ liệu ra

Một số nguyên duy nhất là số buổi hoà nhạc lớn nhất.

Ràng buộc

• $2\le n\le 6000$
• $1\le r_i\le {10}^6$
• $1\le a_j,b_j\le n$
• Dữ liệu đảm bảo các con đường tạo thành một cây.

Ví dụ