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 is guaranteed that the answer will not exceed 10¹⁴.

Example

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

Output:
42