A11501. Imbalance Value of a Tree

You are given a tree $T$ consisting of $n$ vertices. A number is written on each vertex; the number written on vertex $i$ is $a_{i}$ . Let's denote the function $I(x,y)$ as the difference between maximum and minimum value of $a_{i}$ on a simple path connecting vertices $x$ and $y$ .

Your task is to calculate .

The first line contains one integer number $n$ ( $1<=n<=10^{6}$ ) — the number of vertices in the tree.

The second line contains $n$ integer numbers $a_{1}$ , $a_{2}$ , ..., $a_{n}$ ( $1<=a_{i}<=10^{6}$ ) — the numbers written on the vertices.

Then $n-1$ lines follow. Each line contains two integers $x$ and $y$ denoting an edge connecting vertex $x$ and vertex $y$ ( $1<=x,y<=n$ , $x≠y$ ). It is guaranteed that these edges denote a tree.

Print one number equal to .