Cho đồ thị liên thông gồm \(n\) đỉnh và \(n-1\) cạnh. Đỉnh thứ \(i\) có trọng số \(c_i\). Ký hiệu \(len(u,v)\) là số cạnh đi qua trên đường đi từ \(u\) tới \(v\) sao cho không có cạnh nào được đi qua quá một lần. Dễ thấy với mỗi cặp \((u,v)\) \((1 \le u, v \le n)\) bất kỳ, đường đi từ \(u\) tới \(v\) này luôn là duy nhất. Ta ký hiệu \(g(u,v)\) là trọng số của một đường đi từ \(u\) tới \(v\) được tính bằng công thức:

• \(g(u,v) = len(u,v) \times min(c_u, c_v)\).

Yêu cầu

• Xác định đường đi có trọng số lớn nhất trong đồ thị.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương \(n (n \lt 10^5)\);
• Dòng thứ hai chứa \(n\) số nguyên dương \(c_1, c_2, ..., c_n\) \((ci \le 10^9 ∀i = 1,2,...,n)\);
• \(n - 1\) dòng cuối cùng, dòng thứ \(i\) chứa \(2\) số nguyên \(u_i, v_i\) xác định cạnh nối trực tiếp giữa \(u_i\) và \(v_i\) \((1 \le u_i, v_i \le n)\).

Dữ liệu ra

• Một số nguyên duy nhất là trọng số lớn nhất tìm được.

Input 1

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

Output 1

21