markdown

F. 树的失衡值

时间限制：每个测试点 $4$ 秒
内存限制：每个测试点 $256$ MB
输入：标准输入
输出：标准输出

题目描述

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

你的任务是计算：

输入

• 第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 树的节点数。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）—— 每个节点上的数字。
• 接下来 $n-1$ 行，每行包含两个整数 $x$ 和 $y$，表示连接节点 $x$ 和节点 $y$ 的一条边（$1 \le x, y \le n$，$x \neq y$）。数据保证这些边构成一棵树。

输出

输出一个整数，表示所求的和。

样例

输入

4
2 2 3 1
1 2
1 3
1 4

输出

6