Phương Nam có \(N\) khu vực hành chính, được đánh số từ \(1\) đến \(N\), được kết nối liên thông bởi \(N −1\) con đường tạo thành dạng cây trong lý thuyết đồ thị. Mỗi khu vực tương ứng với một đỉnh của cây, mỗi con đường tương ứng với một cạnh của cây. Nhắc lại, cây là một đồ thị vô hướng, liên thông và không có chu trình. Mỗi khu vực người ta gán cho một giá trị biểu thị mức độ phát triển khu vực đó, khu vực thứ \(i\) có có giá trị \(A_i\).

Nhằm quy hoạch phát triển các khu vực một cách hiệu quả, người ta đánh giá một cụm \(S\) các khu vực liên thông nhau thông qua các con đường nối giữa chúng trong cụm đó bởi một độ hiệu quả. Giá trị độ hiệu quả này được tính bằng hiệu của giá trị lớn nhất trong số các giá trị khu vực thuộc \(S\) và giá trị nhỏ nhất trong số các giá trị khu vực thuộc \(S\). Nói cách khác, với một cụm liên thông \(S\), giá trị của \(S\) là \(max_{u \in S} A_u − min_{u \in S} A_u\).

Người ta muốn chia toàn bộ \(N\) khu vực thành các cụm khu vực riêng biệt, mỗi cụm bao gồm một
hoặc nhiều khu vực liên thông nhau bởi các con đường nối các khu vực trong cụm đó và đánh giá
độ hiệu quả trên mỗi cụm. Tổng độ hiệu quả của một cách chia như vậy được tính bằng tổng giá
trị của các cụm liên thông trong cách chia đó.

Yêu cầu: Hãy tìm cách chia toàn bộ \(N\) khu vực thành các cụm có tổng độ hiệu quả lớn nhất.

Input

• Dòng thứ nhất chứa một số nguyên \(N\) \((1 \le N \le 3 \cdot 10^5)\) là số lượng khu vực ở Phương Nam.
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots , A_N\) \((1 \le A_i \le 10^9)\) mô tả độ phát triển của khu vực tương ứng.
• Dòng thứ \(i\) trong $$ dòng tiếp theo chứa hai số nguyên \(u_i, v_i\) \((1 \le u_i, v_i \le N)\) mô tả một con đường nối hai khu vực \(u_i\) và \(v_i\). Dữ liệu đảm bảo các con đường này tạo thành một cây.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• In ra một số nguyên duy nhất là tổng độ hiệu quả lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(30\%\) số test): \(N \le 20\).
• Subtask \(2\) (\(30\%\) số test): \(N \le 2000\) và tất cả các đỉnh có bậc không quá \(2\).
• Subtask \(3\) (\(20\%\) số test): Tất cả các đỉnh có bậc không quá \(2\).
• Subtask \(4\) (\(20\%\) số test): Không có ràng buộc gì thêm.

Example

4
3 8 9 1
1 2
2 3
3 4

13

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

15