Độ mất cân bằng

Khi nghiên cứu về lý thuyết đồ thị, Thuận đưa ra một đặc trưng cho cây.

Cho một cây gồm \(n\) đỉnh, đỉnh \(i\) \((1 \le i \le n)\) có trọng số \(w_i\).
Với hai đỉnh \(i, j\), gọi \(f(i,j)\) là độ mất cân bằng giữa \(i\) và \(j\), được định nghĩa như sau:

Xét đường đi đơn trên cây từ \(i\) đến \(j\) (bao gồm cả \(i\) và \(j\)).
Gọi \(W_{\max}\) là trọng số lớn nhất và \(W_{\min}\) là trọng số nhỏ nhất trong các đỉnh nằm trên đường đi đó.
Khi đó
$
f(i,j) = W_{\max} - W_{\min}.
$

Độ mất cân bằng \(T\) của cây được định nghĩa là tổng độ mất cân bằng củ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\).

\InputFile

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

\OutputFile

• In ra một số nguyên là giá trị \(T\).

\Scoring

• (20%) Subtask 1: \(n \le 700\);
• (20%) Subtask 2: \(n \le 7000\);
• (20%) Subtask 3: \(1 \le w_i \le 2\);
• (20%) Subtask 4: \(n \le 10^5\);
• (20%) Subtask 5: \(n \le 10^6\).

\Examples
\beginexample
\exmp
4
1 1 2 3
1 2
1 3
1 4

8

\exmp
4
1 2 2 2
1 2
2 3
3 4

3

\endexample

\Note
Với mỗi cặp có thứ tự \((i,j)\), ta xét đường đi từ \(i\) đến \(j\), lấy trọng số lớn nhất và nhỏ nhất trên đường đi đó để tính \(f(i,j)\), sau đó cộng cho mọi \(i, j\) từ \(1\) đến \(n\).
Lưu ý rằng \(f(i,i)=0\), và tổng \(T\) tính trên các cặp có thứ tự.

\endproblem