给你一棵由 n 个顶点组成的树 T。每个顶点上都写有一个数字;写在顶点 i 上的数字是 ai。让我们将函数 I(x, y) 表示为连接顶点 x 和 y 的简单路径上 ai 的最大值和最小值之间的差。
您的任务是计算 $$\sum_{i=1}^{n}\sum_{j=i}^{n}I(i,j)$$。
输入
第一行包含一个整数 n (1 ≤ n ≤ 106) — 树中的顶点数。
第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 106) — 写在顶点上的数字。
接下来是 n - 1 行。每行包含两个整数 x 和 y,表示连接顶点 x 和顶点 y 的边(1 ≤ x,y ≤ n,x ≠ y)。保证这些边代表一棵树。
输出
打印一个等于 $$\sum_{i=1}^{n}\sum_{j=i}^{n}I(i,j)$$ 的数字。
示例
输入 #1
4 2 2 3 1 1 2 1 3 1 4
输出 #1
6