给你一棵含有 $n$ 个节点的无根树。第 $i$ 个节点有一个权值 $a_i$。

树中一个连通分量的价值定义为该连通分量中所有节点权值的最大值与最小值之差。你的任务是删除树中的一些边，将其划分为若干个连通分量，使得所有连通分量的价值之和最大。

输出划分后可能的最大价值之和。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示树中节点的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示节点的权值。

接下来的 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示节点 $u$ 和节点 $v$ 之间的一条边。保证给定的边构成一棵树。

由于输入数据量较大，请使用快速的输入输出方法。

输出格式

输出一个整数——划分树后，所有连通分量的最大可能价值之和。

样例

输入样例 1

8
1 3 7 5 2 8 4 6
1 2
1 3
1 4
3 5
5 6
3 7
7 8

输出样例 1

14

输入样例 2

7
5 9 9 6 6 3 2
3 5
4 6
2 6
5 4
7 2
4 1

输出样例 2

13

说明

在第一个样例中，一种最优的划分方式为：$\{1, 2, 3, 4\}, \{5, 6\}, \{7, 8\}$。这 $3$ 个连通分量的价值分别为 $6, 6, 2$。