There is an undirected tree where each vertex is numbered from $1$ to n$,$ and each contains a data value. The sum of a tree is the sum of all its nodes' data values. If an edge is cut, two smaller trees are formed. The difference between two trees is the absolute value of the difference in their sums.

Given a tree, determine which edge to cut so that the resulting trees have a minimal difference between them, then return that difference.

Example

data$=[1,2,3,4,5,6]$

edges$=[(1,2),(1,3),(2,6),(3,4),(3,5)]$

In this case, node numbers match their weights for convenience. The graph is shown below.

The values are calculated as follows:

Edge Tree $1$ Tree $2$ Absolute

Cut Sum Sum Difference

$18135$

$29123$

$36159$

$441713$

$551611$

The minimum absolute difference is $3.$

Note: The given tree is always rooted at vertex $1.$

Function Description

Complete the cutTheTree function in the editor below.

cutTheTree has the following parameter$($s$)$:

int data$[$n$]$: an array of integers that represent node values

int edges$[$n$-1][2]$: an $2$ dimensional array of integer pairs where each pair represents nodes connected by the edge

Returns

int: the minimum achievable absolute difference of tree sums

Input Format

The first line contains an integer n$,$ the number of vertices in the tree.

The second line contains n space$-$separated integers, where each integer u denotes the node$[$u$]$ data value, data$[$u$].$

Each of the n$-1$ subsequent lines contains two space$-$separated integers u and v that describe edge u $<->$ v in tree t$.$

Constraints

$3<=$n$<=10^5$

$1<=$data$[$u$]<1001,$ where $1<=$u$<=$n

Sample Input

STDIN Function

$-------------$

$6$ data$[]$ size n $=6$

$100200100500100600$ data $=[100,200,100,500,100,600]$

$12$ edges $=[[1,2],[2,3],[2,5],[4,5],[5,6]]$

$23$

$25$

$45$

$56$

Sample Output

$400$