X 公司有 $N$ 名员工。公司拥有严格的树状层级结构——CEO（首席执行官）位于顶端（树的根节点），他拥有若干名直接下属，这些下属也有自己的直接下属，以此类推，直到到达普通员工（树的叶子节点），他们没有任何下属。

员工编号为 $1$ 到 $N$ 的整数。CEO 的编号为 $1$，但其他编号与层级结构无关。每名员工都有一定的经验值，第 $i$ 名员工的经验值记为非负整数 $W_i$。

公司有许多小组项目需要完成，管理层决定将所有员工分成不同的小组（团队），以满足以下条件：

• 每个团队必须至少包含一人，且每个人必须恰好属于一个团队。
• 每个团队必须仅由彼此连续的下属组成。一组员工 $j_1, j_2, j_3, j_4 \dots$ 是一个合法的团队，当且仅当 $j_2$ 是 $j_1$ 的直接下属，$j_3$ 是 $j_2$ 的直接下属，$j_4$ 是 $j_3$ 的直接下属，以此类推。

管理层已知，在一个小组项目完成后，分配给该项目的团队总经验值会增加 $W_{\max} - W_{\min}$，其中 $W_{\max}$ 是团队成员中的最大经验值，$W_{\min}$ 是团队成员中的最小经验值。公司总的经验值增加量等于所有团队经验值增加量之和。管理层希望通过将员工划分为最优的团队配置，使得公司总经验值增加量最大化，同时遵循上述两个条件。

任务

编写一个程序 experience 来计算公司可能获得的最大总经验值增加量。

输入格式

第一行包含一个整数 $N$ —— 公司员工的人数。 第二行包含 $N$ 个空格分隔的非负整数 $W_1, W_2, \dots, W_N$ —— 公司每名员工的经验值。 接下来有 $N - 1$ 行，每行包含两个空格分隔的整数 $u$ 和 $v$，表示公司内的从属关系 —— 编号为 $v$ 的员工是编号为 $u$ 的员工的直接下属。

输出格式

程序应输出一个整数 —— 公司可能获得的最大总经验值增加量。

数据范围

• $1 \le N \le 100\,000$
• $0 \le W_i \le 10^9$
• 在占总分 $20\%$ 的测试点中，$N \le 20$
• 在占总分 $50\%$ 的测试点中，$N \le 5000$
• 在占总分 $10\%$ 的测试点中，每名员工最多只有一名直接下属

样例

输入 1

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

输出 1

6

说明

一种使总经验值增加量最大化的配置是 $\{1, 5, 3\}, \{6, 2, 4\}, \{7\}$。还有另一种配置具有相同的最大总经验值增加量 —— $\{1, 5\}, \{3\}, \{6, 2, 4\}, \{7\}$。