Cho đồ thị liên thông gồm ~n~ đỉnh và ~n - 1~ cạnh (tức là một cây). Đỉnh thứ ~i~ có trọng số ~c_i~. Ký hiệu ~\mathrm{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 đường đi từ ~u~ tới ~v~, được tính bằng công thức:

$$ g(u, v) = \mathrm{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

• Dòng đầu chứa số nguyên dương ~n~ (~n < 10^5~);
• Dòng thứ hai chứa ~n~ số nguyên dương ~c_1, c_2, \ldots, c_n~ (~c_i \le 10^9~ với mọi ~i = 1, 2, \ldots, n~);
• ~n - 1~ dòng cuối cùng, dòng thứ ~i~ chứa hai 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~).

Kết quả

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

Ví dụ

PROPATH.INP

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

PROPATH.OUT

21

Giải thích: Các cạnh của cây: 1-2, 1-6, 2-5, 3-5, 2-4. Trọng số các đỉnh 1..6 lần lượt là 5, 9, 8, 7, 10, 2. Một số đường đi: ~g(1, 5) = 2 \times 5 = 10~; ~g(3, 4) = 3 \times 7 = 21~; ~g(6, 3) = 4 \times 2 = 8~; ~g(4, 6) = 3 \times 2 = 6~; ... Đường đi có trọng số lớn nhất là đường đi từ 4 tới 3.

Giới hạn

• Subtask 1: ~u_i = i, v_i = i + 1~ với mọi ~i = 1, 2, \ldots, n - 1~; ~n \le 100~.
• Subtask 2: ~n \le 100~.
• Subtask 3: ~n \le 4000~.
• Subtask 4: ~n \le 10^5~.