In the country of Nocrae, there exists ~N~ villages, the ~i~th of which contains ~a_i~ people. The Nocraean villages are connected to each other by ~N-1~ roads of length ~1~ such that it is possible to reach any village from any other village while only using these roads. The villages wish to establish a meeting place where all of the villagers can meet up. Knowing that any single village might be too far for some people to go to, the villages decided to choose two distinct villages as meeting places for the villagers to meet up. The inconvenience of each villager is defined to be the distance between his village and the closer of the two meeting places. The villagers want to know the minimum possible total inconvenience that is achievable.

Constraints

In all subtasks,
~2 \le N \le 300\,000~
~1 \le a_i \le 10^6~

Subtask 1 [10%]

~N \le 100~

Subtask 2 [10%]

The number of roads going to or from each village is at most ~2~.

Subtask 3 [30%]

~N \le 3\,000~

Subtask 4 [50%]

No additional constraints.

Input Specification

The first line contains one integer, ~N~.
The next line contains ~N~ space-separated integers, ~a_1, a_2, \dots, a_n~.
~N-1~ lines follow, each one containing two space-separated integers, ~u_i~ and ~v_i~, describing the road connecting the ~u_i~th and ~v_i~th villages.

Output Specification

Output one integer, the minimum possible total inconvenience.

Sample Input 1

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

Sample Output 1

11

Explanation for Sample Output 1

A possible choice of meeting places is villages ~1~ and ~4~. It is impossible to achieve an inconvenience lower than ~11~.

Sample Input 2

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

Sample Output 2

9

Explanation for Sample Output 2

A possible choice of meeting places is villages ~4~ and ~5~. It is impossible to achieve an inconvenience lower than ~9~.