Sau nhiều năm mở rộng khu vực quản lý, Minh hiện phụ trách một hệ thống gồm \(n\) khu đất, được nối với nhau bởi \(n-1\) con đường. Hệ thống đường đảm bảo giữa hai khu đất bất kỳ tồn tại đúng một đường đi duy nhất, tức là tạo thành một cây. Mỗi khu đất \(i\) có một độ màu mỡ \(a_i\). Minh muốn xây dựng một hệ thống tưới tiêu sao cho mỗi khu đất được cấp nước từ một trong ba trạm bơm. Một trạm bơm được đặt tại một khu đất. Nước từ trạm có thể truyền qua các con đường đến những khu đất được nó quản lý. Tuy nhiên, để tránh việc một trạm phải quản lý quá nhiều đất, Minh đưa ra quy định: Mỗi khu đất phải thuộc đúng một trạm bơm. Các khu đất thuộc cùng một trạm phải tạo thành một thành phần liên thông. Vì vậy, bằng cách chọn hai khu đất làm vị trí đặt trạm và xác định vùng quản lý thích hợp, toàn bộ cây phải được chia thành đúng \(3\) vùng liên thông. Giá trị của một vùng là tổng độ màu mỡ của tất cả khu đất trong vùng đó. Một cách chia được gọi là cân bằng nếu chênh lệch giữa vùng có tổng độ màu mỡ lớn nhất và vùng có tổng độ màu mỡ nhỏ nhất không vượt quá \(D\).

Minh muốn biết: Giá trị nhỏ nhất của \(D\) mà với nó tồn tại một cách chia cây thành \(3\) vùng thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\), trong đó \(a_i\) là độ màu mỡ của khu đất \(i\).
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\), cho biết có một con đường nối trực tiếp khu đất \(u\) và \(v\).

Output

• In ra một số nguyên duy nhất là giá trị nhỏ nhất của \(D\).

Ràng buộc

• \(3 \leq n \leq 2\cdot 10^5\)
• \(1 \leq a_i \leq 10^9\)

Example

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

2

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

2