题目描述

薯条哥有一棵包含$n$个结点的树，每个结点有一个人，处在第$i$个结点的人想吃恰好$i$个苹果。但他手里有$a_i$个苹果，可能不够吃，也可能太多了。

他们每次传递可以向树上相邻的结点传递1个苹果，薯条哥想知道，让所有人都恰好获得他想吃的苹果的数量总共需要有多少次

传递?

输入描述

第一行输入一个整数$n(1 \le n \le 10^5)$。

第二行输入$n$个整数$a_i$，保证所有$a_i$都为非负整数，且和恰好等于$\frac{n\times (n+1)}{2}$

接下来$n-1$行，每一行输出两个整数$u,v(1 \le u,v \le n)$,表示结点$u$和结点$v$有一条边。

输出描述

一行一个整数，表示最小次数。

样例

输入

4
3 1 4 2
1 2
1 3
2 4

输出

6

样例解释

结点3传递1次苹果给结点1。此时苹果数量为[4,1,3,2]。
结点1传递共3次苹果给结点2。此时苹果数量为[1,4,3,2]
结点2传递共2次苹果给结点4。此时苹果数量为[1,2,3,4]。