Imbalance Value of a Tree

给定一棵树，每个顶点都被写上了一个数，第 $i$ 个顶点写上的数是 $a_i$。定义一个函数 $I(x,y)$ 表示从顶点 $x$ 到 $y$ 的简单路径上 $a_i$ 的最大值和最小值的差。 你要求出 $\sum_{i=1}^{n}\sum_{j=i}^{n}I(i,j)$。 输入格式： 第一行一个正整数 $n(1\le n\le 10^6)$，表示树上节点个数。 第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，表示树上每个节点写的数值。 接下来 $n-1$ 行，每行两个正整数 $x,y$，表示一条边连接节点 $x$ 和 $y$（$1\le x,y\le n$，$x\ne y$）。保证图是一棵树。 输出格式： 输出一个数，表示 $\sum_{i=1}^n\sum_{j=i}^nI(i,j)$。

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 .

4
2 2 3 1
1 2
1 3
1 4

6