Khi nghiên cứu về lý thuyết đồ thị, Thuận đã tìm ra một đặc trưng cho cây. Cụ thể, với cây
gồm \(n\) đỉnh, đỉnh \(i (1 \le i \le n)\) có trọng số là \(w[i]\), gọi \(f(i, j)\) là độ mất cân bằng giữa hai
đỉnh \(i\) và \(j (1 \le i, j \le n)\), trọng số \(f(i, j)\) được tính bằng chênh lệnh trọng số giữa đỉnh có
trọng số lớn nhất với đỉnh có trọng số bé nhất trong các đỉnh nằm trên đường đi từ \(i\) đến \(j\)
(bao gồm cả \(i, j\)). Độ mất cân bằng \(T\) của cây là tổng độ mất cân bằng giữa mọi cặp đỉnh.

Yêu cầu: Cho một cây và trọng số các đỉnh, hãy tính giá trị \(T\).

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu chứa số nguyên dương \(n\);
• Dòng thứ hai gồm \(n\) số nguyên \(w_1, w_2, ..., w_n (1 \le w_i \le 10^6)\);
• Dòng thứ \(k (1 \le k \le n - 1)\) trong \(n - 1\) dòng tiếp theo chứa hai số \(u_k, v_k (1 \le u_k, v_k \le n)\)
  mô tả cạnh thứ \(k\) của cây.

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là giá trị \(T\) tính được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 700\);
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 7000\);
• Subtask \(3\) (\(20\%\) số điểm): \(1 \le w_i \le 2\);
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^5\);
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^6\);

Example

4
1 1 2 3
1 2
1 3
1 4

8

4
1 2 2 2
1 2
2 3
3 4

3