It is Christmas Eve, and Santa is delivering presents!

There are ~N~ houses in the world which he has already delivered presents to. Each house ~i~ has already been delivered ~a_i~ presents. However, he noticed that he gave some houses more presents than others. He wants all the houses to end up with the same number of presents.

Thankfully, Santa has unlimited elves at his disposal. The houses are connected by ~N-1~ two-way roads where each house is able to reach every other house through some series of roads. A single elf can carry a present from any house to a house adjacent to it (i.e. the elf can only carry the present across ~1~ road). Presents may be carried multiple times, and multiple presents can be carried across a single path.

What is the minimum number of elves needed to distribute the presents evenly?

Constraints

For all test cases, ~1 \le N \le 10^5~, ~0 \le a_i \le 10^9~, the sum of all ~a_i~ for ~1 \le i \le N~ is divisible by ~N~.

Subtask 1 [10%]

~1 \le N, a_i \le 5~

Subtask 2 [10%]

~1 \le N, a_i \le 16~

Subtask 3 [30%]

~1 \le N, a_i \le 10^3~

Subtask 4 [50%]

No additional constraints.

Input Specification

First line: ~N~ (the number of houses).

Second line: ~N~ space-separated integers describing ~a_i~ for each ~1 \le i \le N~ (the initial number of presents in each home).

Next ~N-1~ lines: Two space-separated integers ~u_i~ and ~v_i~ (~1 \le u_i, v_i \le N~) indicating that a road connects houses ~u_i~ and ~v_i~.

Output Specification

One integer: The minimum number of elves needed for every house to have the same number of presents.

Sample Input

4
2 1 1 4
1 2
1 3
1 4

Output for Sample Input

4

Explanation for Sample Case

Santa can get ~4~ elves to carry presents

1. From house ~1~ to house ~2~,
2. From house ~4~ to house ~1~,
3. From house ~1~ to house ~3~,
4. From house ~4~ to house ~1~.

Afterwards, each house has exactly ~2~ presents. It can be proven that this is an optimal solution.