Problem Statement

You are given a tree with $N$ vertices and $N-1$ edges. Edge $i$ ($1 \le i \le N-1$) connects vertex $A_i$ and vertex $B_i$.
Each vertex $i$ ($1 \le i \le N$) has a weight $W_i$.

You choose $2$ edges of this tree and delete them (keeping the vertices), which splits the tree into $3$ trees.

For each tree, compute the sum of the weights of the vertices it contains. Let these sums be $S_1, S_2, S_3$.
Minimize the maximum difference between the weights of the $3$ trees, that is, $\max(S_1, S_2, S_3) - \min(S_1, S_2, S_3)$.

Constraints

• $3 \le N \le 2 \times 10^5$
• $1 \le W_i \le 10^9$
• $1 \le A_i, B_i \le N$
• $A_i \neq B_i$
• The given graph is a tree.
• All input values are integers.

Input

The input is given from standard input in the following format.

$N$
$W_1\ W_2\ \dots\ W_N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_{N-1}\ B_{N-1}$

The $1$st line gives the number of vertices $N$, the $2$nd line gives the vertex weights $W_1, W_2, \ldots, W_N$, and the following $N-1$ lines give the information that the $i$-th edge connects vertex $A_i$ and vertex $B_i$.

Output

Print the minimum value of (maximum - minimum) of the weights of the $3$ trees as an integer on $1$ line. End the output with a newline.

Sample

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

10

4
10 5 6 7
1 2
1 3
1 4

9

9
147020957 677362324 450052904 16845359 45810150 325394266 982528921 104391635 490669916
6 2
9 6
4 1
3 2
5 3
2 1
8 3
7 6

625419147