Experience

Company X has $N$ employees. The company has a strict hierarchical tree structure. The CEO (chief executive officer) is at the top (the root of the tree) and has some number of direct subordinates, who have direct subordinates of their own, and so on down to the regular employees, who have no subordinates (the leaves of the tree).

The employees are numbered from 1 to $N$. The CEO has number 1, and the other numbers have nothing to do with the hierarchy. Each employee has some experience: employee $i$ has experience $W_i$, a non-negative integer.

The company has a large number of group projects to complete, so the management splits all of the employees into teams. The split must satisfy both conditions below.

• Each team consists of at least one person, and each person belongs to exactly one team.
• Each team consists only of people who are consecutive subordinates of one another. A group of employees $j_1, j_2, j_3, j_4, \dots$ is a valid team when $j_2$ is a direct subordinate of $j_1$, $j_3$ is a direct subordinate of $j_2$, $j_4$ is a direct subordinate of $j_3$, and so on.

After a group project is finished, the total experience of the team assigned to that project increases by $W_{\max} - W_{\min}$, where $W_{\max}$ is the largest experience and $W_{\min}$ is the smallest experience among the members of the team. The total experience increase for the company is the sum of the increases of all teams. The management wants to maximize the total increase for the company by choosing the best possible split under the two conditions above.

Write a program that computes the maximum possible experience increase for the company.

The first line contains a single integer $N$, the number of employees in the company.

The second line contains $N$ space separated non-negative integers $W_1, W_2, \dots, W_N$, the experience of each employee.

Each of the next $N - 1$ lines contains two space separated integers $u$ and $v$ in that order. Employee $v$ is a direct subordinate of employee $u$.

Print one integer, the maximum total experience increase for the company.

• $1 \le N \le 100000$
• $0 \le W_i \le 10^9$

The picture shows a company of 7 employees. The number inside a circle is the employee number, and the red number next to it is that employee's experience. One split that reaches the maximum total increase is {1, 5, 3}, {6, 2, 4}, {7}. The split {1, 5}, {3}, {6, 2, 4}, {7} reaches the same maximum.