Nhật Bản có \(N\) thành phố, được nối với nhau bằng \(N-1\) con đường hai chiều. Từ một thành phố bất kỳ có thể đi đến mọi thành phố khác bằng các con đường này. Mỗi thành phố có một tòa nhà trụ sở chính quyền; tòa nhà ở thành phố \(i\) cao \(H_i\).

Nhân dịp Olympic Tin học Quốc tế được tổ chức tại Nhật Bản, người ta muốn lên kế hoạch cho một chuyến tham quan để chào đón các thí sinh trên thế giới. Chuyến đi bắt đầu tại một thành phố, liên tiếp đi theo các con đường sang thành phố khác và kết thúc tại một thành phố. Không thành phố nào được ghé thăm quá một lần.

Người ta sẽ trang trí tòa nhà trụ sở chính quyền ở một số thành phố trên hành trình. Nhà thiết kế yêu cầu chiều cao của các tòa nhà được trang trí phải tăng nghiêm ngặt theo thứ tự ghé thăm. Cụ thể, nếu các thành phố có tòa nhà được trang trí lần lượt là \(i_1,i_2,\ldots,i_k\) theo thứ tự trên hành trình, thì phải có

Không bắt buộc phải trang trí tòa nhà tại mọi thành phố đi qua.

Bạn được tự do chọn thành phố bắt đầu, thành phố kết thúc và các thành phố có tòa nhà được trang trí.

Yêu cầu

Hãy tính số tòa nhà lớn nhất có thể trang trí.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\), là số thành phố.
• \(N\) dòng tiếp theo: dòng thứ \(i\) chứa số nguyên \(H_i\), là chiều cao tòa nhà ở thành phố \(i\).
• \(N-1\) dòng tiếp theo: dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\) cách nhau bởi dấu cách, cho biết con đường thứ \(i\) nối thành phố \(A_i\) với thành phố \(B_i\).

Dữ liệu ra

In ra đầu ra chuẩn một số nguyên là số tòa nhà lớn nhất có thể trang trí.

Ràng buộc

• \(2\le N\le100\,000\).
• \(1\le H_i\le1\,000\,000\,000\) với \(1\le i\le N\).
• \(1\le A_i<B_i\le N\) với \(1\le i\le N-1\).
• Các con đường nối tất cả các thành phố thành một mạng liên thông.
• Mọi giá trị trong đầu vào đều là số nguyên.

Phân nhóm

• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn \(N\le100\).
• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(N\le2\,000\).

Ví dụ

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

4