CF915F.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 .

给你一棵包含 $ n $ 个顶点的树 $ T $。每个顶点上写有一个数字；顶点 $ i $ 上写的数字为 $ a_i $。定义函数 $ I(x, y) $ 为连接顶点 $ x $ 和 $ y $ 的简单路径上所有 $ a_i $ 值的最大值与最小值之差。

你的任务是计算

The first line contains one integer number n (1 ≤ n ≤ 106) — the number of vertices in the tree.

The second line contains n integer numbers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 106) — 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.

第一行包含一个整数 $ n $（$ 1 \leq n \leq 10^6 $）——树中顶点的数量。

第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 1 \leq a_i \leq 10^6 $）——写在各个顶点上的数字。

接下来是 $ n-1 $ 行，每行包含两个整数 $ x $ 和 $ y $，表示连接顶点 $ x $ 和顶点 $ y $ 的一条边（$ 1 \leq x, y \leq n $，且 $ x \neq y $）。保证这些边构成一棵树。

Print one number equal to .

输出一个等于 的数字。