A path of rooted tree is a "straight-chain" iff for each node pair (u, v) on the path, either u is the ancestor of v, or v is the the ancestor of u.  

Given a rooted tree with weighted nodes, decompose it into several "straight-chain",so that the quadratic sum of all "straight-chain" is minimum. The weight of a "straight-chain" is the sum of the weights of all the nodes on this chain.

Input

The first line contains an integer N(N<=1200000),the number of nodes.

The second line contains n integers w1,w2,...,wn.wi represents ith-node's weight.

The following n-1 lines, each line describes an edge of the tree.

The nodes are numbered from 1 to n, and 1 is the root.

Output

An integer,the minimum quadratic sum.
It's guaranteed that the answer will not exceed 10^14. 

Example

Input:
7
-4 -10 5 4 1 -1 -5
1 2
2 3
1 4
2 5
5 6
5 7
Output:
42