Thành phố NQ là thành phố có tiềm năng về ngành du lịch vô cùng to lớn với nhiều danh lam thắng cảnh độc đáo. Tuy nhiên, chính quyền trước đây vẫn chưa thật sự quan tâm và khai phá hết những tiềm năng này. Thế nhưng trong những năm gần đây, tình hình đã dần được thay đổi với rất nhiều dự án và sự đầu tư mạnh tay vào lĩnh vực du lịch của nhiều tổ chức. Và một trong những thay đổi đó chính là việc quy hoạch lại các tuyến đường giao thông. Có $N$ danh lam thắng cảnh ở thành phố NQ. Chính quyền dự tính sẽ xây dựng $N-1$ tuyến đường hai chiều, mỗi tuyến đường nối trực tiếp 2 danh lam thắng cảnh với nhau sao cho luôn tồn tại đường đi (trực tiếp hoặc gián tiếp) giữa 2 danh lam thắng cảnh bất kỳ. Mỗi danh lam thắng cảnh sẽ có một độ thu hút khách du lịch riêng, danh lam thứ i sẽ có sức thu hút $a_i$. Một tour du lịch sẽ bắt đầu từ danh lam thứ $u$ và kết thúc ở danh lam thứ $v$ $(u<v)$ sao cho mỗi danh lam được thăm tối đa 1 lần và sẽ có sức thu hút là sức thu hút của danh lam có sức thu hút lớn nhất trên đường đi đó. Nhiệm vụ của bạn là tính tổng sức thu hút của tất cả các tour du lịch.

INPUT

• Dòng đầu tiên là số nguyên dương N $(N\ge 2)$, là số danh lam thắng cảnh của thành phố NQ.
• Dòng tiếp theo là gồm $N$ số nguyên dương $a_1,a_2,...,a_N(a_i\le {10}^6)$ là sức thu hút của các thành phố.
• $N-1$ dòng tiếp theo, gồm 2 số nguyên dương $u$ và $v$, cho biết có 1 đường đi 2 chiều nối trực tiếp 2 thành phố thứ $u$ và $v$

OUTPUT

• Gồm 1 số nguyên duy nhất là tổng sức thu hút của tất cả các tour du lịch.

Ví dụ

Input 1

3
3 1 5
1 2
1 3

Output 1

13

Input 2

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

Output 2

255

Subtask 1: $25$% số test thỏa $N\le 300$

Subtask 2: $25$% số test thỏa $N\le 3000$

Subtask 3: $25$% số test thỏa $N\le 300000$, đường đi giữa 2 danh lam bất kỳ có độ dài bé hơn $3$

Subtask 4: $25$% số test thỏa $N\le 300000$

Giải thích test 1

• Tour du lịch từ danh lam thứ $1$ tới danh lam thứ $2$ có sức hút là $3$.
• Tour du lịch từ danh lam thứ $1$ tới danh lam thứ $3$ có sức hút là $5$.
• Tour du lịch từ danh lam thứ $2$ tới danh lam thứ $3$ có sức hút là $5$.
• Tổng sức hút của tất cả các tour du lịch là $3+5+5=13$.