Độ chênh lệch của cây

Cho một cây $T$ gồm $n$ đỉnh được đánh số từ $1$ đến $n$. Trên đỉnh thứ $i$ có ghi số nguyên $a_i$.

Với hai đỉnh $x$ và $y$ bất kỳ, gọi $I(x,y)$ là hiệu giữa giá trị lớn nhất và giá trị nhỏ nhất trong các số được ghi trên những đỉnh nằm trên đường đi đơn nối $x$ với $y$ (tính cả hai đỉnh đầu mút). Đặc biệt, $I(x,x)=0$.

Hãy tính tổng

$$\sum _{i=1}^n\sum _{j=i}^{n}I(i,j)$$

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$, số đỉnh của cây.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x$ và $y$, mô tả một cạnh nối đỉnh $x$ với đỉnh $y$. Dữ liệu đảm bảo các cạnh này tạo thành một cây.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng cần tính.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a_i\le {10}^6$
• $1\le x,y\le n$ và $x\ne y$

Ví dụ