# Towers solution codeforces

## Towers solution codeforces

You are given a tree with nn vertices numbered from 11 to nn. The height of the ii-th vertex is hihi. You can place any number of towers into vertices, for each tower you can choose which vertex to put it in, as well as choose its efficiency. Setting up a tower with efficiency ee costs ee coins, where e>0e>0.

It is considered that a vertex xx gets a signal if for some pair of towers at the vertices uu and vv (uvu≠v, but it is allowed that x=ux=u or x=vx=v) with efficiencies eueu and evev, respectively, it is satisfied that min(eu,ev)hxmin(eu,ev)≥hx and xx lies on the path between uu and vv.

Find the minimum number of coins required to set up towers so that you can get a signal at all vertices.

Input

The first line contains an integer nn (2n2000002≤n≤200000) — the number of vertices in the tree.

The second line contains nn integers hihi (1hi1091≤hi≤109) — the heights of the vertices.

Each of the next n1n−1 lines contain a pair of numbers vi,uivi,ui (1vi,uin1≤vi,ui≤n) — an edge of the tree. It is guaranteed that the given edges form a tree.

Output

Print one integer — the minimum required number of coins.

Examples
input

Copy
3
1 2 1
1 2
2 3

output

Copy
4
input

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

output

Copy
7
input

Copy
2
6 1
1 2

output

Copy
12
Note

In the first test case it’s optimal to install two towers of height 22 at vertices 11 and 33.

In the second test case it’s optimal to install a tower of height 11 at vertex 11 and two towers of height 33 at vertices 22 and 55.

In the third test case it’s optimal to install two towers of height 66 at vertices 11 and 22.