小可可的院子可以看作为一棵 $n$ 个点的树。

冬天，这棵树的每一个点上都堆积了深度为 $a_i$ 的雪。不过小可可有一台铲雪机，他每一次可以开着铲雪机从一个点沿着最短路到另外一个点，让经过的点的雪的深度减一。由于铲雪机非常暴躁，所以如果地上没有雪，这辆车甚至会把地皮带走。因此他不能开车经过没有雪的点。

由于铲雪很麻烦，所以小可可想知道，最少要开几次铲雪机才能把雪扫完呢？

输入格式

​第一行一个数 $n$，表示树的点数。

​第二行 $n$ 个非负整数 $a_i$ 表示雪的深度。

​接下来 $n-1$ 个数对描述了树每一条边所连接的点。

输出格式

​输出仅一行一个数表示答案。

5
5 4 5 3 2
1 2
2 3
3 4
3 5

6

样例解释 #1：

满足条件的其中一组方案为：

• 第一次：铲雪机扫点 $1$ 至点 $5$ 的雪，此时每个点雪的深度分别为 $4\ 3\ 4\ 3\ 1$。
• 第二次：重复上一次的操作，此时每个点雪的深度分别为 $3\ 2\ 3\ 3\ 0$。
• 第三次：铲雪机扫点 $1$ 至点 $4$ 的雪，此时每个点雪的深度分别为 $2\ 1\ 2\ 2\ 0$。
• 第四次：重复上一次的操作，此时每个点雪的深度分别为 $1\ 0\ 1\ 1\ 0$。
• 第五次：铲雪机扫点 $3$ 至点 $4$ 的雪，此时每个点雪的深度分别为 $1\ 0\ 0\ 0\ 0$。
• 第六次：铲雪机扫点 $1$ 至点 $1$ 的雪，此时每个点雪的深度分别为 $0\ 0\ 0\ 0\ 0$。

共六次操作，此为最少操作数。

样例 2

见选手目录下的 snow/snow2.in 和 snow/snow2.ans。

样例 3

见选手目录下的 snow/snow3.in 和 snow/snow3.ans。

数据范围

​测试点 $1\sim 9$ 满足 $1\le n\le 6$，$0\le a_i\le 5$。

​测试点 $10\sim 16$ 满足 $1\le n\le 100$，$0\le a_i\le 100$。

​测试点 $17\sim 25$ 无特殊限制。

​对于所有数据，保证 $1\le n\le 2\times 10^5$，$1\le a_i\le 10^9$。